15. 3Sum

LeetCode Problems

← Prev Next →

In this tutorial we will solve 15. 3Sum from leetcode.

Table of Content

Reference
Problem Statement
Approach
Code
Complexity

Reference: 15. 3Sum

1. Two Sum

167. Two Sum II - Input Array Is Sorted

Problem statement

We are given an integer array nums and we are asked to return all the triplets that adds up to zero.

Triples, nums[i] + nums[j] + nums[k] = 0 where i != j, j != k and k != i.

Our result must not contain duplicate triplets.

Example from leetcode.

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.

Constraints:

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

Approach

We will first sort the input array in ascending order. After sorting the array the problem becomes very similar to 167. Two Sum II - Input Array Is Sorted.

If we have two or more identical adjacent elements in the sorted array then we will ignore to avoid duplicate tuples.

Let us try to solve the first example nums = [-1,0,1,2,-1,-4].

result = []

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

sort(nums)

index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
          ^   ^               ^
          i   l               r

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-4) + (-1) + 2
    = -3
sum < 0
  -> increment l
  -> l is now 2


result = []
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
          ^       ^           ^
          i       l           r

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-4) + (-1) + 2
    = -3
sum < 0
  -> increment l
  -> l is now 3


result = []
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
          ^           ^       ^
          i           l       r

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-4) + 0 + 2
    = -2
sum < 0
  -> increment l
  -> l is now 4


result = []
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
          ^               ^   ^
          i               l   r

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-4) + 1 + 2
    = -1
sum < 0
  -> increment l
  -> l is now 5
now, l is not less than r,
  -> increment i by 1
  -> i is now 1


result = []
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
              ^   ^           ^
              i   l           r

is nums[i] === nums[i-1] ? no
  -> proceed further

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-1) + (-1) + 2
    = 0
sum == 0
  -> add the triplet to result
    -> result = [[-1, -1, 2]]
  -> increment l
  -> l is now 3
  -> decrement r
  -> r is now 4


result = [[-1, -1, 2]]
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
              ^       ^   ^
              i       l   r

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = (-1) + 0 + 1
    = 0
sum == 0
  -> add the triplet to result
    -> result = [[-1, -1, 2], [-1, 0, 1]]
  -> increment l
  -> l is now 4
  -> decrement r
  -> r is now 3
now, l is not less than r,
  -> increment i by 1
  -> i is now 2


result = [[-1, -1, 2], [-1, 0, 1]]
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
                  ^   ^       ^
                  i   l       r

is nums[i] === nums[i-1] ? yes
  -> increment i by 1 and check again


result = [[-1, -1, 2], [-1, 0, 1]]
index =   0   1   2   3   4   5
nums  = [-4, -1, -1,  0,  1,  2]
                      ^   ^   ^
                      i   l   r

is nums[i] === nums[i-1] ? no
  -> proceed further

is l < r ? yes
sum = nums[i] + nums[l] + nums[r]
    = 0 + 1 + 2
    = 3
sum > 0
  -> decrement r
  -> r is now 4

Result is [[-1, -1, 2], [-1, 0, 1]].

Code

JavaScript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var threeSum = function(nums) {
  nums.sort((a,b) => a - b);

  let result = [];

  for(let i = 0; i < nums.length - 2; i++) {
    // ignore duplicates
    if (i > 0 && nums[i] === nums[i-1]) {
      continue;
    }

    let left = i + 1;
    let right = nums.length - 1;

    while(left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum < 0) {
        left++;
      } else if (sum > 0) {
        right--;
      }
      else {
        result.push([nums[i], nums[left], nums[right]]);
        
        // ignore duplicates and move to the right
        while(left < right && nums[left] === nums[left + 1]) {
          left++;
        }
        
        // ignore duplicates and move to the left
        while(left < right && nums[right] === nums[right - 1]) {
          right--;
        }
        
        // move left and right pointers closer
        left++;
        right--;
      }
    }
  }
  return result;
};

Complexity

Time complexity: O(n^2)

Sort of array of size n will take O(nlogn) time. Then we have the loops for n elements using two pointers. Therefore, time complexity will be O(n^2).

Space complexity: O(n^2)

The result array stores the triplets. In worst case, all the triplets will be unique, the result array will hold up to O(n^2) triples.

← Prev Next →

Array, Hash map and Set

Two Pointers