Question

LeetCode Link | 18. Four Sum | Medium

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

  • 0 <= a, b, c, d < n
  • a, b, c, and d are distinct.
  • nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Constrains

  • 1 <= nums.length <= 200
  • -10^9 <= nums[i] <= 10^9
  • -10^9 <= target <= 10^9

Examples

Example 1

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Solution Approach

Method: Two-pointers

Constrains

  • Unique

If this question allow duplicate triplets, this could be solve using hash method by finding if other two values sum up equal to 0 - (a + b) which just like question 454. Four Sum II.

Concept Explanation

The solution for “4 Sum”, similar to the problem 15. 3 Sum, which employs the two-pointer technique. The basic approach for this question is to add an additional for loop on top of the “3 Sum” solution.

The two-pointer method for this question involves two layers of for loops, with nums[i] and nums[j] as fixed values, and still utilizes the lo and hi indices as two pointers within the loop to find combinations where nums[i] + nums[j] + nums[lo] + nums[hi] == target. The time complexity for “3 Sum” is 𝑂(𝑛2), and for “4 Sum” it increases to 𝑂(𝑛3).

Similarly, the same approach can be applied to “5 Sum”, “6 Sum”, and so on……

For problem 15, “3 Sum”, the two-pointer method reduces the original brute force solution from 𝑂(𝑛3) to 𝑂(𝑛2). For “4 Sum”, the two-pointer method reduces the brute force solution from 𝑂(𝑛4) to 𝑂(𝑛3).

Code

  • Time complexity: O(n3)
  • Space complexity: O(1)

TypeScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
function fourSum(nums: number[], target: number): number[][] {
    let result: number[][] = [];
    // Sort nums in ascending order
    nums.sort((a, b) => a - b);

    /* Iterate nums and find 4 number that meets following requirements:
     *      Find a + b + c + d = target
     *      a = nums[i], b = nums[j], c = nums[lo], d = nums[hi]
     *
     * Set interval for i to `nums.length - 3` and j to `nums.length - 2` is because:
     *      a = nums[length - 4], b = nums[length - 3], c = nums[length - 2], d = nums[length - 1]
     * This is the largest possible quadruplets
     */
    for (let i = 0; i < nums.length - 3; i++) {
        // Skip duplicate value for "a"
        if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
            for (let j = i + 1; j < nums.length - 2; j++) {
                // Skip duplicate value for "b"
                if (j === i + 1 || (j > i + 1 && nums[j] !== nums[j - 1])) {
                    let lo: number = j + 1;                         // left boundary
                    let hi: number = nums.length - 1;               // right boundary
                    let sum: number = target - nums[i] - nums[j];   // Desired value for (c + d) that a + b + (c + d) = 0

                    // Keep finding value until interval closed
                    while (lo < hi) {
                        // Found desired value
                        if (nums[lo] + nums[hi] === sum) {
                            // Add correct quadruplets into result
                            result.push([nums[i], nums[j], nums[lo], nums[hi]]);
                            // Skip duplicate value for "c"
                            while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
                            // Skip duplicate value for "d"
                            while (lo < hi && nums[hi] === nums[hi - 1]) hi--;

                            // Smaller interval, remove used number
                            lo++;
                            hi--;
                        }
                        // Try higher "c" so that it could reach the sum
                        else if (nums[lo] + nums[hi] < sum) lo++;
                        // Try lower "d" to reach the sum
                        else hi--;
                    }
                }
            }
        }
    }
    return result;
};

Conclusion

When dealing this type of question, think if it is the best way to use hash method even it looks like a hash method problem. Also, consider all possible duplicates before you actually starting write the code.