/ Data Structure and Algorithms  

Leetcode 15: 3Sum

Question



Given an array, find all unique triplets that add up to 0

Similar Questions

Solution 1

Brute force solution. We need 3 nested for loops. If we found that nums[i] + nums[j] + nums[k] == target, then need to check if the solution already exist (which takes O(n)). So the overall complexity is O(n3). Space complexity O(1).

Solution 2

Reference https://leetcode.com/problems/3sum/discuss/7380/Concise-O(N2) as a O(n2) solution.

The main idea is to iterate through the array, fix one number as sum, and find another 2 numbers that add up to -sum. The clever thing is how to find the other two numbers in O(n).

The achieve that, first we need to sort the array.

Then we get num[i] as target , and try to find if there are 2 element add up to -num[i]. As the array is sorted, we can use 2 pointers (low and high) at head and tail, so find 2 elements takes O(n).

  • num[low] + num[high] > target, high = high -1. As we are greater than target, we need to decrease the high pointer to make sum smaller.
  • num[low] + num[high] < target, low++. As we are smaller than target, we need to increase the low pointer to make sum larger.

To avoid add duplicate result, we need to move the pointer to point to different number with num[low] and num[high]. For example, let’s say the array is [-2, -1, 0, 0, 1, 1, 2, 3]. The num[i] = -2. We found that num[1] + num[5] + num[i] = 0. To continue the loop, we need to move high = 5 to high = 3. If we don’t have this step, then when the loop continues, we will have num[1] + num[4] + num[i] = 0 and this result is duplicate with the result we already have.

Code:

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
List<List<Integer>> results = new ArrayList<>();

// sort the array
Arrays.sort(nums);

for (int i = 0; i < nums.length; i++) {
    // skip the same number in array when we choose the number as sum target
    if (i > 0 && nums[i] == nums[i - 1]) {
        continue;
    }

    // start the loop to find remaining 2 numbers
    int low = i + 1;
    int high = nums.length - 1;

    int target = -nums[i];

    while (low < high) {
        // find the 2 numbers
        if (nums[low] + nums[high] == target) {
            results.add(Arrays.asList(nums[low], nums[high], nums[i]));

            low++;
            high--;

            // skip same number to avoid duplicate
            while (low < high && nums[low] == nums[low - 1]) {
                low++;
            }

            // skip same number to avoid duplicate
            while (low < high && nums[high] == nums[high + 1]) {
                high--;
            }
        } else if (nums[low] + nums[high] > target) {
            high--;
        } else {
            low++;
        }
    }
}

return results;