Problem 1: Find N Unique Integers Sum up to Zero

Given an integer n, any array of n unique integers that sum to 0 can be returned.

Example 1:

Input: n = 5

Output: [-7,-1,1,3,4]

Explanation: These arrays are also correct [-5,-1,1,2,3], [-3,-1,2,-2,4].

Example 2:

Input: n = 3

Output: [-1,0,1]

Example 3:

Input: n = 1

Output: [0]

Constraints:

• 1 <= n <= 1000

Solution 1:

/**
 * @param {number} n
 * @return {number[]}
 */
var sumZero = function(n) {
    const result = [];
    let start = 0;
    while (n > 1) {
        start += 1;
        result.push(start, -start);
        n -= 2;
    }
    if (n === 1) {
        result.push(0);
    }
    return result;
};

Solution 2 (More concise):

/**
 * @param {number} n
 * @return {number[]}
 */
var sumZero = function(n) {
    const result = [];
    if (n % 2 === 1) result.push(0);
    for (let i = 1; result.length < n; i++) {
        result.push(i);
        result.push(-i);
    }
    return result;
};

Explanation:

The first solution uses a while loop that adds pairs (1, -1), (2, -2), etc., and appends 0 if n is odd. The second solution is more elegant: it starts with 0 for odd n and then continues adding pairs until the array length reaches n.

---

Problem 2: All Elements in Two Binary Search Trees

Return a list containing all integers from two binary search trees, sorted in ascending order.

Example 1:

Input: root1 = [2,1,4], root2 = [1,0,3]

Output: [0,1,1,2,3,4]

Example 2:

Input: root1 = [0,-10,10], root2 = [5,1,7,0,2]

Output: [-10,0,0,1,2,5,7,10]

Example 3:

Input: root1 = [], root2 = [5,1,7,0,2]

Output: [0,1,2,5,7]

Example 4:

Input: root1 = [0,-10,10], root2 = []

Output: [-10,0,10]

Example 5:

Input: root1 = [1,null,8], root2 = [8,1]

Output: [1,1,8,8]

Constraints:

• Each tree has at most 5000 nodes.
• Each node value is in the range [-10^5, 10^5].

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * @param {TreeNode} root1
 * @param {TreeNode} root2
 * @return {number[]}
 */

const dfs = (root, result) => {
    if (!root) return;
    result.push(root.val);
    if (root.left) dfs(root.left, result);
    if (root.right) dfs(root.right, result);
};

var getAllElements = function(root1, root2) {
    const values = [];
    dfs(root1, values);
    dfs(root2, values);
    values.sort((a, b) => a - b); // Must provide comparator for correct numerical sort
    return values;
};

Explanation:

This problem is straightforward: traverse both trees (any order, but depth-first is used here), collect all values, and then sort the combined array. It's important to provide a custom comparator to sort() because the default sort converts numbers to strings, which can lead to incorrect ordering for numbers with different digit counts.

---

Problem 3: Jump Game III

Given an array of non-negative integers arr, you start at index start. When at index i, you can jump to i + arr[i] or i - arr[i]. Determine if you can reach any index with value 0. You cannot jump outside the array.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5

Output: true

Explanation: All possible paths to reach index 3 (value 0):

• Index 5 -> Index 4 -> Index 1 -> Index 3
• Index 5 -> Index 6 -> Index 4 -> Index 1 -> Index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0

Output: true

Explanation: Index 0 -> Index 4 -> Index 1 -> Index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2

Output: false

Explanation: It's impossible to reach index 1 (value 0).

Constraints:

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length

Solution 1 (Recursive with memo):

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    const visited = new Set();
    
    const dfs = (index) => {
        if (index < 0 || index >= arr.length || visited.has(index)) return false;
        if (arr[index] === 0) return true;
        visited.add(index);
        return dfs(index + arr[index]) || dfs(index - arr[index]);
    };
    
    return dfs(start);
};

Solution 2 (Iterative BFS):

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    const n = arr.length;
    const queue = [start];
    const visited = new Array(n).fill(false);
    visited[start] = true;
    
    while (queue.length) {
        const current = queue.shift();
        if (arr[current] === 0) return true;
        
        const nextForward = current + arr[current];
        if (nextForward < n && !visited[nextForward]) {
            visited[nextForward] = true;
            queue.push(nextForward);
        }
        
        const nextBackward = current - arr[current];
        if (nextBackward >= 0 && !visited[nextBackward]) {
            visited[nextBackward] = true;
            queue.push(nextBackward);
        }
    }
    
    return false;
};

Solution 3 (Iterative with explicit stack):

/**
 * @param {number[]} arr
 * @param {number} start
 * @return {boolean}
 */
var canReach = function(arr, start) {
    const n = arr.length;
    const stack = [start];
    const visited = new Set();
    
    while (stack.length) {
        const idx = stack.pop();
        if (visited.has(idx)) continue;
        if (arr[idx] === 0) return true;
        visited.add(idx);
        
        const forward = idx + arr[idx];
        const backward = idx - arr[idx];
        
        if (forward >= 0 && forward < n && !visited.has(forward)) {
            stack.push(forward);
        }
        if (backward >= 0 && backward < n && !visited.has(backward)) {
            stack.push(backward);
        }
    }
    
    return false;
};

Explanation:

This is a classic graph traversal problem. The array defines edges from each index to i + arr[i] and i - arr[i] (if within bounds). We need to see if any zero-valued node is reachable from the start node.

Key points to remember:

• Use a visited set/array to avoid infinite loops (since there could be cycles).
• The recursive solution is elegant but may cause stack overflow for large inputs; iterative solutions are safer.
• The BFS solution using a queue works well.

---

Problem 4: Verbal Arithmetic Puzzle

Given an equation, represented by words on the left and result on the right, determine if the equation is solvable under these rules:

• Each character is decoded as a single digit (0-9).
• Each pair of different characters must map to different digits.
• Each words[i] and result are decoded as numbers without leading zeros.
• The sum of the numbers on the left (the words) equals the number on the right (the result).

Return true if the equation is solvible, otherwise false.

Example 1:

Input: words = ["SEND","MORE"], result = "MONEY"

Output: true

Explanation: Map 'S'->9, 'E'->5, 'N'->6, 'D'->7, 'M'->1, 'O'->0, 'R'->8, 'Y'->2

Then "SEND" + "MORE" = "MONEY" -> 9567 + 1085 = 10652

Example 2:

Input: words = ["SIX","SEVEN","SEVEN"], result = "TWENTY"

Output: true

Explanation: Map 'S'->6, 'I'->5, 'X'->0, 'E'->8, 'V'->7, 'N'->2, 'T'->1, 'W'->3, 'Y'->4

Then "SIX" + "SEVEN" + "SEVEN" = "TWENTY" -> 650 + 68782 + 68782 = 138214

Example 3:

Input: words = ["THIS","IS","TOO"], result = "FUNNY"

Output: true

Example 4:

Input: words = ["LEET","CODE"], result = "POINT"

Output: false

Constraints:

• 2 <= words.length <= 5
• 1 <= words[i].length, result.length <= 7
• words[i] and result contain only uppercase English letters
• The number of different characters used in the expression is at most 10.

Solution 1 (Backtracking with pruning):

/**
 * @param {string[]} words
 * @param {string} result
 * @return {boolean}
 */
var isSolvable = function(words, result) {
    // Collect all unique letters
    const letters = new Set();
    const leadingLetters = new Set();
    
    // Add all words
    for (const word of words) {
        for (const ch of word) letters.add(ch);
        leadingLetters.add(word[0]);
    }
    // Add result
    for (const ch of result) letters.add(ch);
    leadingLetters.add(result[0]);
    
    const letterList = Array.from(letters);
    const used = new Array(10).fill(false);
    const mapping = {};
    
    // Calculate coefficients for each letter
    const coeff = {};
    for (const ch of letters) {
        coeff[ch] = 0;
    }
    
    for (const word of words) {
        const n = word.length;
        for (let i = 0; i < n; i++) {
            const ch = word[n - 1 - i];
            coeff[ch] += Math.pow(10, i);
        }
    }
    
    const n = result.length;
    for (let i = 0; i < n; i++) {
        const ch = result[n - 1 - i];
        coeff[ch] -= Math.pow(10, i);
    }
    
    // DFS with pruning
    const dfs = (index) => {
        if (index === letterList.length) {
            // Check sum
            let sum = 0;
            for (const ch of letters) {
                sum += coeff[ch] * mapping[ch];
            }
            return sum === 0;
        }
        
        const ch = letterList[index];
        const startDigit = leadingLetters.has(ch) ? 1 : 0;
        
        for (let digit = startDigit; digit <= 9; digit++) {
            if (!used[digit]) {
                used[digit] = true;
                mapping[ch] = digit;
                if (dfs(index + 1)) return true;
                used[digit] = false;
            }
        }
        
        return false;
    };
    
    return dfs(0);
};

Solution 2 (Alternative backtracking):

/**
 * @param {string[]} words
 * @param {string} result
 * @return {boolean}
 */
var isSolvable = function(words, result) {
    const letters = new Set();
    const leading = new Set();
    const leftCoeff = {};
    const rightCoeff = {};
    const powers = [1, 10, 100, 1000, 10000, 100000, 1000000, 10000000];

    // Calculate coefficients for left side
    for (const word of words) {
        const n = word.length;
        for (let i = 0; i < n; i++) {
            const c = word[n - 1 - i];
            letters.add(c);
            leftCoeff[c] = (leftCoeff[c] || 0) + powers[i];
        }
        leading.add(word[0]);
    }

    // Calculate coefficients for right side
    const n = result.length;
    for (let i = 0; i < n; i++) {
        const c = result[n - 1 - i];
        letters.add(c);
        rightCoeff[c] = (rightCoeff[c] || 0) + powers[i];
    }
    leading.add(result[0]);

    const letterList = Array.from(letters);
    const used = new Array(10).fill(true);
    const assignment = {};

    const dfs = (index) => {
        if (index >= 0) {
            const ch = letterList[index];
            const start = leading.has(ch) ? 1 : 0;
            for (let digit = start; digit <= 9; digit++) {
                if (used[digit]) {
                    used[digit] = false;
                    assignment[ch] = digit;
                    if (dfs(index - 1)) return true;
                    used[digit] = true;
                }
            }
            return false;
        } else {
            // All letters assigned, check equation
            let leftSum = 0;
            for (const c in leftCoeff) {
                leftSum += assignment[c] * leftCoeff[c];
            }
            let rightSum = 0;
            for (const c in rightCoeff) {
                rightSum += assignment[c] * rightCoeff[c];
            }
            return leftSum === rightSum;
        }
    };

    return dfs(letterList.length - 1);
};

Explanation:

This is a constraint satisfaction problem that can be solved with backtracking. The key optimizations are:

1. Leading digit constraint: Letters that appear as the first character of any word or result cannot be assigned 0.
2. Coefficient calculation: Instead of summing at the end by converting strings to numbers (which requires re-computation every time), we can precompute the coefficient (power of 10) for each letter based on its position. The sum of (coefficient * digit) for all letters must be 0 for the equation to hold.
3. Pruning: We can prune invalid assignments early.

This reduces the search space significantly.