15. 3Sum


Problem Description

This problem asks us to find all the unique triplets in an array that can combine to give a sum of zero. A triplet in this context is defined as a set of three numbers [nums[i], nums[j], nums[k]] where each number comes from a different position in the array, indicated by i, j, and k. Importantly, we need to ensure that:

  1. The indices i, j, and k are all different.
  2. The sum of the numbers at those indices is zero (nums[i] + nums[j] + nums[k] == 0).
  3. No triplet is repeated in the result.

Our goal is to identify all such combinations, ensuring that each combination of three numbers is unique within the result set. This problem is a classic example of a challenge involving array manipulation and the identification of specific patterns within a numerical set.

Intuition

To arrive at the solution for this problem, we will follow a two-step approach. First, we sort the array in non-decreasing order. The sorting helps us in two ways: it makes it easy to avoid adding duplicate triplets and allows us to use the two-pointer technique effectively.

After sorting, the array is processed with a loop that effectively tries out each number as a potential candidate for the first number of the triplet. This candidate is referred to as nums[i]. Starting from i = 0, we will check whether nums[i], when added to any two other numbers in the array to its right, sums to zero.

To expedite the process and avoid checking combinations that are guaranteed to fail or are redundant, we make use of the following insights:

  1. If the current number nums[i] is greater than zero, because the array is sorted, any combination involving this and subsequent numbers will be greater than zero. Since no sum with a positive total can equal zero, we can break out of the loop early.

  2. If nums[i] is the same as the previous number nums[i-1], we skip the current value to prevent processing the same triplet scenario, which would lead to duplicates.

Once a valid nums[i] is chosen, we employ a while loop using two pointers, j and k, that start after i (for j) and at the end of the array (for k). We calculate the sum of nums[i], nums[j], and nums[k]. If the sum is:

  • Less than zero, we move j to the right to increase the sum (nums[j] will be larger).
  • Greater than zero, we shift k to the left to decrease the sum (because nums[k] will get smaller).
  • Exactly zero, we have found a valid triplet and add it to our solution set. We then move both j and k pointers, skipping over any duplicates to look for additional triplets starting with nums[i].

We repeat this process for every index i until the second last element, and collect all unique triplets that give us a sum of zero.

Learn more about Two Pointers and Sorting patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

Which data structure is used to implement recursion?

Solution Approach

The code implements a sort and two-pointer strategy to find all unique triplets summing to zero in the nums array. Below are the detailed steps taken by the implementation, following the Reference Solution Approach:

  1. Sort the Array: First, we sort the array using nums.sort(). Sorting is beneficial as it orders the elements, allowing us to employ the two-pointer method effectively, and it makes it easier to avoid duplicates since duplicate values will be adjacent in a sorted array.

  2. Iterate Over Possible First Elements of Triplets: We look at each number in the nums array (up until the third-to-last element) to be the potential first element of our triplet. This is achieved with a for loop: for i in range(n - 2).

  3. Early Breaks and Continues: Inside this loop, we have some conditions that help us eliminate unnecessary checks:

    • If the current number nums[i] is greater than zero, we can break out of the loop. This is because any triplet involving a positive starting number will have a sum greater than zero.
    • If the current number is the same as the previous number (and i is not 0), we use continue to skip to the next iteration to avoid checking for duplicates.
  4. Two-Pointer Technique: For each i, we use two pointers, j and k, initialized to i + 1 and n - 1 (the end of the array), respectively. We then enter a while loop, which will continue as long as j is less than k.

  5. Find the Triplets: Within the while loop, we calculate the sum x of nums[i], nums[j], and nums[k] and compare it to zero:

    • If x is less than zero, we increment j since we need a larger number to increase the sum.
    • If x is greater than zero, we decrement k as we need a smaller number to decrease the sum.
    • If x is zero, we have found a valid triplet and we add [nums[i], nums[j], nums[k]] to ans. After storing the triplet, we move both j and k past any duplicates to ensure we don't find duplicates in subsequent iterations.
  6. Return the Result: Once all numbers have been considered for the first element of the triplet, and all valid j, k pairs have been evaluated, we return ans. This list contains all the unique triplets that add up to zero.

This solution has a time complexity of O(n^2) and a space complexity of O(log n) due to the sort operation, assuming that the sort() method used takes O(log n) space for the internal stack during a sorting algorithm like quicksort or mergesort. However, if the sorting does not take extra space, then the space complexity will only be O(1), which is the space taken by the output array and the pointers used.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

Example Walkthrough

Let's walk through the solution approach using a small example. Consider the array nums = [-1, 0, 1, 2, -1, -4].

Following the steps in the solution approach:

  1. Sort the Array: We start by sorting nums, resulting in [-4, -1, -1, 0, 1, 2].

  2. Iterate Over Possible First Elements of Triplets: We start looking through the array for potential first elements of the triplet. The loop runs from the start of the array to n - 3, where n is the length of the sorted nums array.

  3. Early Breaks and Continues: As we loop through, if we find a number larger than zero (nums[i] > 0), we can break out of the loop. In our example, all numbers from the index 0 to n - 3 will be considered since the break condition does not become true.

We also skip the second element, which is -1, same as the first, using continue to avoid duplicates.

  1. Two-Pointer Technique: We start the two-pointer process with i, j, and k as follows:

    • i = 0: We choose -4 as the first element.
    • j = i + 1: j starts at -1 (the element right after -4).
    • k = n - 1: k starts at 2 (the last element).
  2. Find the Triplets: In the while loop, we find sums of nums[i] + nums[j] + nums[k] and adjust j and k accordingly:

    • The first sum is -4 + -1 + 2 = -3, which is less than zero. We increment j to move to the next larger number, which is another -1.
    • Now, the sum is -4 + -1 + 2 = -3, still less than zero. We increment j again and move to 0.
    • With j on 0, the sum is -4 + 0 + 2 = -2, and we continue incrementing j to move to 1.
    • The sum is now -4 + 1 + 2 = -1, which is still less than zero, so we move j again, but now we've reached the end, and the while loop ends for this i.

Next, with i = 1, we find:

  • i = 1 (but this is skipped because it's the same as i = 0).
  • i = 2, we have the first element as -1, j = 3 and k = 5, so we test the combination -1 + 0 + 2, which sums to 1. The sum is greater than zero, so we decrement k.
  • Now, k is 4, and j is 3, so we test -1 + 0 + 1, which sums to 0. We've found a valid triplet [-1, 0, 1].

Each time we find a triplet, we move both j and k while they point to the same number to avoid duplicates. In this case, there are no duplicates, and we are done with this iteration.

  1. Return the Result: After evaluating all potential starting points, the solution returns the list of unique triplets found. In this case, [[-1, 0, 1]] is the only unique triplet that sums to zero.

The implementation would return [[−1, 0, 1]] as the output.

Following the outlined process, we can find all possible unique triplets in the array that can combine to give a sum of zero.

Not Sure What to Study? Take the 2-min Quiz:

Which data structure is used to implement recursion?

Python Solution

1class Solution:
2    def three_sum(self, nums):
3        # Sort the input array to facilitate the two-pointer approach.
4        nums.sort()
5        # Get the length of the array.
6        n = len(nums)
7        # Initialize the list to store the triplets.
8        triplets = []
9
10        # Iterate through the array.
11        for i in range(n - 2):
12            # If the current number is greater than 0, since the array is sorted,
13            # no three numbers can add up to zero.
14            if nums[i] > 0:
15                break
16            # Skip the same element to avoid duplicate triplets.
17            if i > 0 and nums[i] == nums[i - 1]:
18                continue
19            # Set the two pointers, one just after the current element,
20            # and the other at the end of the array.
21            left, right = i + 1, n - 1
22
23            # While the left pointer is less than the right pointer.
24            while left < right:
25                # Calculate the sum of the current three elements.
26                current_sum = nums[i] + nums[left] + nums[right]
27                # If the sum is less than zero, move the left pointer to the right.
28                if current_sum < 0:
29                    left += 1
30                # If the sum is greater than zero, move the right pointer to the left.
31                elif current_sum > 0:
32                    right -= 1
33                # If the sum is zero, we've found a valid triplet.
34                else:
35                    # Add the triplet to the result.
36                    triplets.append([nums[i], nums[left], nums[right]])
37                    # Move both the left and right pointers to continue searching.
38                    left, right = left + 1, right - 1
39                    # Skip duplicate elements by moving the left pointer to the right.
40                    while left < right and nums[left] == nums[left - 1]:
41                        left += 1
42                    # Skip duplicate elements by moving the right pointer to the left.
43                    while left < right and nums[right] == nums[right + 1]:
44                        right -= 1
45
46        # Return the list of found triplets.
47        return triplets
48
49# Example of calling the function:
50# solution = Solution()
51# result = solution.three_sum([-1, 0, 1, 2, -1, -4])
52# print(result)  # Expected output: [[-1, -1, 2], [-1, 0, 1]]
53

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    public List<List<Integer>> threeSum(int[] nums) {
7        // Sort the array to make the two-pointer technique applicable
8        Arrays.sort(nums);
9      
10        // Initialize the list to store the triplets
11        List<List<Integer>> triplets = new ArrayList<>();
12      
13        // Get the length of the array
14        int length = nums.length;
15      
16        // Iterate over the array, looking for the first element of the triplet
17        for (int first = 0; first < length - 2 && nums[first] <= 0; ++first) {
18            // Skip duplicate elements to avoid duplicate triplets
19            if (first > 0 && nums[first] == nums[first - 1]) {
20                continue;
21            }
22          
23            // Initialize the second and third pointers
24            int second = first + 1;
25            int third = length - 1;
26          
27            // Use two-pointer technique to find the remaining two elements
28            while (second < third) {
29                int sum = nums[first] + nums[second] + nums[third];
30              
31                // If the sum is less than zero, move the second pointer to the right
32                if (sum < 0) {
33                    ++second;
34                }
35                // If the sum is greater than zero, move the third pointer to the left
36                else if (sum > 0) {
37                    --third;
38                }
39                // If the sum is zero, we've found a valid triplet
40                else {
41                    triplets.add(List.of(nums[first], nums[second], nums[third]));
42                  
43                    // Move the second pointer to the right and skip duplicates
44                    while (second < third && nums[second] == nums[second + 1]) {
45                        ++second;
46                    }
47                    // Move the third pointer to the left and skip duplicates
48                    while (second < third && nums[third] == nums[third - 1]) {
49                        --third;
50                    }
51                  
52                    // Move both pointers for the next potential triplet
53                    ++second;
54                    --third;
55                }
56            }
57        }
58        // Return the list of triplets
59        return triplets;
60    }
61}
62

C++ Solution

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
7        // First, we sort the numbers.
8        std::sort(nums.begin(), nums.end());
9      
10        // This will hold the unique triplets.
11        std::vector<std::vector<int>> result;
12      
13        // Calculate the number of elements.
14        int numElements = nums.size();
15      
16        // Start the first pointer `i` from the beginning of the array
17        // and iterate over the numbers as long as there are at least 
18        // two more elements after it and the current element is not positive.
19        for (int i = 0; i < numElements - 2 && nums[i] <= 0; ++i) {
20            // If this is not the first element and it's the same as the one before,
21            // we skip it to avoid duplicate solutions.
22            if (i > 0 && nums[i] == nums[i - 1]) {
23                continue;
24            }
25          
26            // Pointers `j` and `k` initialize to elements after `i` and the last element respectively.
27            int j = i + 1, k = numElements - 1;
28          
29            // While `j` is before `k` we look for valid triplets.
30            while (j < k) {
31                int sum = nums[i] + nums[j] + nums[k];
32              
33                // If current sum is less than zero, increment `j` to get closer to zero.
34                if (sum < 0) {
35                    ++j;
36                } 
37                // If current sum is greater than zero, decrement `k` to get closer to zero.
38                else if (sum > 0) {
39                    --k;
40                }
41                // If the sum is zero, we found a triplet.
42                else {
43                    // Add the current triplet to the result.
44                    result.push_back({nums[i], nums[j], nums[k]});
45                  
46                    // Increment `j` and decrement `k` to find the next unique triplet.
47                    ++j;
48                    --k;
49                  
50                    // Skip duplicate values from `j` and `k` for the unique triplet.
51                    while (j < k && nums[j] == nums[j - 1]) {
52                        ++j;
53                    }
54                    while (j < k && nums[k] == nums[k + 1]) {
55                        --k;
56                    }
57                }
58            }
59        }
60      
61        // Return the set of triplets found.
62        return result;
63    }
64};
65

Typescript Solution

1function threeSum(nums: number[]): number[][] {
2  // Sort the input array in non-decreasing order
3  nums.sort((a, b) => a - b);
4  const triplets: number[][] = [];
5  const length = nums.length;
6
7  // Iterate through the array looking for triplets
8  for (let first = 0; first < length - 2 && nums[first] <= 0; first++) {
9    // Skip over duplicates for the first element of the triplet
10    if (first > 0 && nums[first] === nums[first - 1]) {
11      continue;
12    }
13
14    // Initialize two pointers for the second and third elements
15    let second = first + 1;
16    let third = length - 1;
17  
18    // Move second and third pointers to find all valid triplets
19    while (second < third) {
20      const sum = nums[first] + nums[second] + nums[third];
21
22      // If the sum is less than zero, move the second pointer to the right to increase sum
23      if (sum < 0) {
24        second++;
25      } 
26      // If the sum is greater than zero, move the third pointer to the left to decrease sum
27      else if (sum > 0) {
28        third--;
29      } 
30      // If the sum is zero, we've found a valid triplet
31      else {
32        triplets.push([nums[first], nums[second], nums[third]]);
33        second++;
34        third--;
35
36        // Skip over duplicates for the second element of the triplet
37        while (second < third && nums[second] === nums[second - 1]) {
38          second++;
39        }
40
41        // Skip over duplicates for the third element of the triplet
42        while (second < third && nums[third] === nums[third + 1]) {
43          third--;
44        }
45      }
46    }
47  }
48
49  // Return the array of all valid triplets
50  return triplets;
51}
52
Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following is a min heap?

Time and Space Complexity

Time Complexity

The time complexity of the given code is O(n^2). This is because there is a nested loop where the outer loop runs for n times (reduced by 2 to avoid unnecessary last iterations due to triplets), and within this loop, there are two pointers that are moving independently towards each other, which in total will lead to n iterations in the worst case. There are no nested loops inside the while loop, so the inner operations are constant time notwithstanding the while conditions which are also O(n). Multiplying these together gives us n * n = n^2, hence O(n^2).

Space Complexity

The space complexity of the code is O(log n) if we don't take the output space into consideration, which would be O(n). The space complexity arises due to the space used by the sorting algorithm, which is typically O(log n) for the commonly used algorithms like QuickSort or MergeSort in many standard programming libraries.

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫