Question

LeetCode Link | 15. Three Sum | Medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Constrains

  • 3 <= nums.length <= 3000
  • -10^5 <= nums[i] <= 10^5

Examples

Example 1

Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0.
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0.
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.

Example 2

Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.

Example 3

Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.

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.

To remove duplicates in hash method, it needs many condition and costs lots of time, which really leads to time out exceeded which is why this question has a such low acceptance.

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
function threeSum(nums: number[]): number[][] {
    let result: Set<string> = new Set();
    let freq: Map<number, number> = new Map();

    // Count the frequency of each number
    for (let num of nums) {
        freq.set(num, (freq.get(num) || 0) + 1);
    }

    for (let i = 0; i < nums.length; i++) {
        freq.set(nums[i], freq.get(nums[i]) - 1);
        for (let j = i + 1; j < nums.length; j++) {
            freq.set(nums[j], freq.get(nums[j]) - 1);
            let complement = 0 - nums[i] - nums[j];
            if (freq.get(complement) > 0) {
                let triplet = [nums[i], nums[j], complement].sort((a, b) => a - b);
                result.add(JSON.stringify(triplet));
            }
            freq.set(nums[j], freq.get(nums[j]) + 1);
        }
        freq.set(nums[i], freq.get(nums[i]) + 1);
    }

    return Array.from(result).map(triplet => JSON.parse(triplet));
}

Time out

Concept Explanation

Using hash methods for this problem may not appropriate because there are many details to consider in the deduplication process, and it can be difficult to write bug-free code directly in an interview.

Using the two-pointer method is more efficient than hash methods for this problem. Let’s take this nums array as an example:

nums = [-1, 0, 1, 2, -1, 4]

first, sort the array, then start a loop with i beginning at index 0. Define left boundary lo at the position i+1 and right boundary hi at the end of the array.

Initial State

The goal is still to find a, b, and c in the array such that a + b + c = 0, where a = nums[i], b = nums[lo], and c = nums[hi].

Next, how do we move lo and hi?

If nums[i] + nums[lo] + nums[hi] < 0, it means the sum of the three numbers is too small. Moving lo to the right increases the sum, continuing until lo meets hi. After lo cross hi, meaning the interval is closed, and it starts with the next i.

Move lo

If it finds a combination that a + b + c = 0, add this triplets into result array. Then it checks if next following lo and hi has the same value, and skip them by increase lo index and decrease hi index since same value will result a duplicate triplet.

Meets requirement

If nums[i] + nums[lo] + nums[hi] > 0, it means the sum of the three numbers is too large. Since the array is sorted, the right index should move left to decrease the sum.

Why the range of i index is i < nums.length - 2?

The largest possible triplets is the last three elements, which is nums[length - 3] + nums[length - 2] + nums[length - 1] = 0 , which means the largest index of i is smaller than nums.length - 2.

Deduplication Logic Thought

In thinking about the deduplication logic for a three-sum problem, the main consideration is the deduplication of the three numbers, a, b, c, corresponding to nums[i], nums[lo], and nums[hi].

Deduplication of a

What if a is repeated? Since a is an element traversed in nums, it should be skipped directly.

But here’s a question: should we check if nums[i] is the same as nums[i + 1], or if nums[i] is the same as nums[i - 1]?

Some might think, aren’t they the same? Actually, they are not!

Both comparisons are with nums[i], but it’s about whether you compare it with the previous one or the next one.

If our approach is like this:

1
2
3
if (nums[i] == nums[i + 1]) {
  ...
}

Then we directly pass cases where duplicate elements appear in the triplet. For example, with the nums= [-1, -1, 2, 4, 6] with a possible data set [-1, -1, 2], when iterating to the first -1, if the next one is also -1, then this data set is passed.

What we need to do is avoid duplicate triplets, but the elements within a triplet can be repeated! So there are two definition of duplication here.

Then it should be written like this:

1
2
3
if (i > 0 && nums[i] == nums[i - 1]) {
    ...
}

Writing it this way means that when we are currently using nums[i], we check if the previous element is the same. Looking at the data {-1, -1, 2}, when iterating to the first -1, as long as there isn’t another -1 before it, then the data set {-1, -1, 2} can still be included in the results.

Deduplication of b and c

You might add additional duplication for the b and c as following code shown (as commented in the code)

1
2
3
4
5
6
7
8
9
10
11
12
while (lo > hi) {
    if (nums[i] + nums[lo] + nums[hi] > 0) {
        hi--;
        // Deduplication for b
        while (lo < hi && nums[hi] == nums[hi + 1]) hi--;
    } else if (nums[i] + nums[lo] + nums[hi] < 0) {
        lo++;
        // Deduplication for c
        while (lo < hi && nums[lo] == nums[hi - 1]) lo++;
    } else {
    }
}

Upon closer consideration, this type of deduplication actually does not help to improve the efficiency of the program.

Taking the deduplication of hi as an example, even without this deduplication logic, the operation of decrementing hi is still completed based on the conditions while (hi > lo) and if (nums[i] + nums[lo] + nums[hi] > 0).

Adding the line while (lo < hi && nums[hi] == nums[hi + 1]) hi--; essentially just pre-executes the necessary logic but does not reduce the logic for decision-making.

The most straightforward thought process is that hi is still decremented one by one, so it doesn’t matter where the decrement takes place.

Therefore, this type of deduplication is unnecessary. It merely advances the deduplication logic.

Code

  • Time complexity: O(n2)
  • 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
function threeSum(nums: number[]): number[][] {
    let result: number[][] = [];
    // Sort nums in ascending order
    nums.sort((a, b) => a - b);

    /* Iterate nums and find 3 number that meets following requirements:
     *      Find a + b + c = 0
     *      a = nums[i], b = nums[lo], c = nums[hi]
     *
     * Set interval to `nums.length - 2` is because:
     *      a = nums[length - 3], b = nums[length - 2], c = nums[length - 1]
     * This is the largest possible triplets
     */
    for (let i = 0; i < nums.length - 2; i++) {
        // Skip duplicate value for "a"
        if (i === 0 || (i > 0 && nums[i] !== nums[i - 1])) {
            let lo = i + 1;             // left bound interval
            let hi = nums.length - 1;   // right bound interval
            let sum = 0 - nums[i];      // Desired value for (b + c) that a + (b + c) = 0
            
            // Keep finding value until interval closed
            while (lo < hi) {
                // Find desired value
                if (nums[lo] + nums[hi] === sum) {
                    // Add correct triplets into result
                    result.push([nums[i], nums[lo], nums[hi]])
                    // Skip duplicate value for "b"
                    while (lo < hi && nums[lo] === nums[lo + 1]) lo++;
                    // Skip duplicate value for "c"
                    while (lo < hi && nums[hi] === nums[hi - 1]) hi--;

                    // Smaller interval
                    lo++;
                    hi--;
                } 
                // Try higher "b" so that it could reach the sum
                else if (nums[lo] + nums[hi] < sum) lo++;
                // Try lower "c" 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.