Three Sum Problem


Description

LeetCode Problem 15. Given an array of integers nums, return all unique triplets (a, b, c) in the array which gives the sum of zero (a + b + c = 0).

Example:

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


Solution

This problem is similar to the two sum problem.

Brute Force Approach

A simple solution is to use the brute force approach.

We loop through the array three times to get three different elements (a, b, c). Then we check whether (a + b + c = 0) is true or not.

If it is true, we add the triplets (a, b, c) to a set to ensure the final solutions do not contain duplicates; otherwise, we keep on searching.

The time complexity of this approach is O(n3), and the space complexity is O(n).

Two Pointer Approach

If the array is sorted, we can use the two pointer approach to reduce the time and space complexity.

We first sort the array in ascending order, the time complexity of this step is O(nlogn).

For each element nums[i] in the array, we set two pointers pointing to the elements larger than nums[i]: the left pointer l points to the smallest element on the right of nums[i], and the right pointer r points to the largest element on the right of nums[i].

We add the three numbers together (nums[i] + nums[l] + nums[r]) and compare it with 0.

If the sum is greater than 0, that means nums[r] is too big for the triplet (and nums[l] is already the smallest possible one), so we move the right pointer one step to the left (r-1) to try a smaller number.

If the sum is smaller than 0, that means nums[l] is too small for the triplet (and nums[r] is already the biggest possible one), so we move the left pointer one step to the right (l+1) to try a bigger number.

If the sum is 0, we find one solution and insert it into a set (to make sure the final solutions do not contain duplicates). Then we move the left pointer one step to the right (l+1), and the right pointer one step to the left (r-1). We move the left pointer one step to the right is because if we only move the right pointer and keep the left pointer pointing to the current number, the new nums[r] will be smaller or equal to the old nums[r]. If it is smaller, the sum of these three numbers will be less than 0. If it is equal, then this solution will be the same as the original one. Same reason applies to why we move the right pointer one step to the left.

Here is a complete walk-through of the approach.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| -1 | 0  | 1  | 2  | -1 | -4 | <--  (Original Array)
| -4 | -1 | -1 | 0  | 1  | 2  | <--  (Sorted Array)
  i    l                   r    <--  (-4 + -1 + 2 = -3 < 0 => l++)
  i         l              r    <--  (-4 + -1 + 2 = -3 < 0 => l++)
  i              l         r    <--  (-4 + 0 + 2 = -2 < 0 => l++)
  i                   l    r    <--  (-4 + 1 + 2 = -1 < 0 => l++)
  i                        lr   <--  (l=r -> i++)
       i    l              r    <--  (-1 + -1 + 2 = 0 => one solution found, l++, r--)
       i         l    r         <--  (-1 + 0 + 1 = 0 => one solution found, l++, r--)
       i         r    l         <--  (l>r => i++)
            i    l         r    <--  (-1 + 0 + 2 = 1 > 0 => r--)
            i    l    r         <--  (-1 + 0 + 1 = 0 => one solution found, l++, r--)
            i    r    l         <--  (l>r => i++)
                 i    l    r    <--  (0 + 1 + 2 = 3 > 0 => r--)
                 i    lr        <--  (l=r => i++)
                      i    lr   <--  (l=r => i++)
                           i    <--  (only one element left, return)

The time complexity can be reduced to O(n2), while the space complexity is still O(n).


Sample C++ Code

This is a C++ implementation of the two pointer approach.

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
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>

using namespace std;

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ans;
    sort(nums.begin(), nums.end());
    set<vector<int>> s;
    
    int l, r;
    for (int i = 0; i < nums.size(); i ++) {
        l = i + 1; 
        r = nums.size() - 1;
        while (l < r) {
            int sum = nums[i] + nums[l] + nums[r];
            if (sum == 0) {
                s.insert({nums[i], nums[l], nums[r]});
                l ++;
                r --;
            } else if (sum > 0) {
                r --;
            } else {
                l ++;
            }
        }
    }
    for (auto x : s) {
        ans.push_back(x);
    }
    return ans;
}

int main() {
    vector<int> nums={-1, 0, 1, 2, -1, -4};
    vector<vector<int>> ans; 
    ans = threeSum(nums);
    for (int i = 0; i < ans.size(); i ++) {
        for (int j = 0; j < ans[i].size(); j ++) {
            cout << ans[i][j] << " ";
        }
        cout << endl;
    }
}




Related Posts

Two Sum Input Array Is Sorted Problem

LeetCode 167. Given an array of integers nums sorted in...

Subarray Sum Divisible By K Problem

LeetCode 974. Given an array of integers nums and an...

Four Sum II Problem

LeetCode 454. Given four lists A, B, C, D of...

Continuous Subarray Sum Problem

LeetCode 523. Given an array of non-negative integers nums and...

Two Sum Less Than K Problem

LeetCode 1099. Given an array of integers nums and an...

Subarray Sum Equals K Problem

LeetCode 560. Given an array of integers nums and an...