Problem 454: Four Sum II

Question

LeetCode Link | 454. Four Sum II | Medium

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

Constrains

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -2^28 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2^28

Examples

Example 1

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
Output: 2
Explanation:
The two tuples are:

1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

Example 2

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
Output: 1

Solution Approach

Method: Unordered Map / Hash Table

Constrains

• Duplicate elements

By using hash method, remove duplicates could execute timeout.

Concept Explanation

This question can be solve in following steps:

1. Define a map where the key stores the sum of each element combination in nums, and value indicates the time of this sum appears.
2. Iterate first two nums (nums1 and nums2), record the sum and the count into the map we defined.
3. Define a variable (resultCount) to store count number that meets the solution requirements.
4. Iterate last two nums (nums3 and nums4), use the current combination tp find the desired sum of first two nums that adds up equal to 0 (0 - (nums3[k] + nums4[l])).
5. Return this variable (resultCount).

Code

• Time complexity: O(n²)
• Space complexity: O(n²)

TypeScript

function fourSumCount(nums1: number[], nums2: number[], nums3: number[], nums4: number[]): number {
    // Key: sum of a & b, Value: count of sum
    const map: Map<number, number> = new Map();
    let resultCount: number = 0;

    // Iterate first two list to get each sum combination
    for (let i of nums1) {
        for (let j of nums2) {
            // Record the number of times for each sum
            map.set(i + j, (map.get(i + j) || 0) + 1);
        }
    }
    // Iterate last two list to get each sum combination
    for (let k of nums3) {
        for (let l of nums4) {
            // Increase count if finds a combination equal to 0
            // 0 - (k + l) -> -k -l
            resultCount += map.get(-k - l) || 0;
        }
    }
    return resultCount;
};

Conclusion

This problem is a classic example of using hash methods. However, not all question in this type use hash methods. Think wisely accroding the constrains and requirements of the question, only use hash method if it only requires you to check if a element exits without its order and duplicates.