Maximum Product of Splitted Binary Tree

Given a binary tree with root node, remove exactly one edge to split the tree into two separate subtrees. The goal is to maximize the product of the sums of both resulting subtrees. Return the result modulo 10^9 + 7.

Approach

The key insight is that during a depth-first search that calculates subtree sums, every node's subtree sum represents a potential smaller subtree after removing the edge connecting it to its parent. By collecting all subtree sums and subtracting each from the total sum, we can compute all possible products and find the maximum.

Solution

function maxProduct(root) {
    const subtreeSums = new Set();
    
    function calculateSubtreeSum(node) {
        if (!node) return 0;
        const currentSum = node.val + calculateSubtreeSum(node.left) + calculateSubtreeSum(node.right);
        subtreeSums.add(currentSum);
        return currentSum;
    }
    
    const totalSum = calculateSubtreeSum(root);
    let maximumProduct = 0;
    
    for (const sum of subtreeSums) {
        const product = sum * (totalSum - sum);
        if (product > maximumProduct) {
            maximumProduct = product;
        }
    }
    
    return maximumProduct % (Math.pow(10, 9) + 7);
}

Minimum Set Size to Remove Half Array

Given an integer array, find the minimum number of distinct integers that need to be removed so that at least half of the array elements are removed.

Approach

Count the frequency of each integer, then sort by frequency in descending order. Remove elements starting from the highest frequency until we've removed at least half of the total elements.

Solution

function minSetSize(arr) {
    const length = arr.length;
    const frequencyMap = arr.reduce((acc, val) => {
        acc[val] = (acc[val] || 0) + 1;
        return acc;
    }, {});
    
    const sortedFrequencies = Object.values(frequencyMap).sort((a, b) => b - a);
    let removedCount = 0;
    
    for (let i = 0; i < sortedFrequencies.length; i++) {
        removedCount += sortedFrequencies[i];
        if (removedCount >= length / 2) {
            return i + 1;
        }
    }
    
    return sortedFrequencies.length;
}

The sort function works by comparing values: when comparing a - b, if positive, the elements swap to arrange in ascending order. For descending order, use b - a.

Jump Game V

Given an integer array and a parameter d, starting from any index, you can jump to another index j if:

• The distance |i - j| is at most d
• arr[i] > arr[j]
• All elements between i and j are smaller than arr[j]

Find the maximum number of indices that can be visited.

Approach

Use dynamic programming with memoization. For each position, compute the maximum reachable positions starting from that index by checking all valid jumps to the left and right within distance d where the destination value is smaller than the current value.

Solution

function maxJumps(arr, d) {
    const n = arr.length;
    const dp = new Array(n).fill(0);
    
    function compute(index) {
        if (dp[index] !== 0) return dp[index];
        
        let maxReach = 1;
        
        // Check positions to the left
        for (let i = index - 1; i >= 0 && index - i <= d && arr[i] < arr[index]; i--) {
            maxReach = Math.max(maxReach, compute(i) + 1);
        }
        
        // Check positions to the right
        for (let i = index + 1; i < n && i - index <= d && arr[i] < arr[index]; i++) {
            maxReach = Math.max(maxReach, compute(i) + 1);
        }
        
        dp[index] = maxReach;
        return maxReach;
    }
    
    for (let i = 0; i < n; i++) {
        if (dp[i] === 0) {
            compute(i);
        }
    }
    
    return Math.max(...dp);
}

This solution efficiently computes the maximum reachable indices using memoization to avoid redundant calculations.