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:
- The indices
i
,j
, andk
are all different. - The sum of the numbers at those indices is zero (
nums[i] + nums[j] + nums[k] == 0
). - 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:
-
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. -
If
nums[i]
is the same as the previous numbernums[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 (becausenums[k]
will get smaller). - Exactly zero, we have found a valid triplet and add it to our solution set. We then move both
j
andk
pointers, skipping over any duplicates to look for additional triplets starting withnums[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.
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:
-
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. -
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)
. -
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 usecontinue
to skip to the next iteration to avoid checking for duplicates.
- If the current number
-
Two-Pointer Technique: For each
i
, we use two pointers,j
andk
, initialized toi + 1
andn - 1
(the end of the array), respectively. We then enter a while loop, which will continue as long asj
is less thank
. -
Find the Triplets: Within the while loop, we calculate the sum
x
ofnums[i]
,nums[j]
, andnums[k]
and compare it to zero:- If
x
is less than zero, we incrementj
since we need a larger number to increase the sum. - If
x
is greater than zero, we decrementk
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]]
toans
. After storing the triplet, we move bothj
andk
past any duplicates to ensure we don't find duplicates in subsequent iterations.
- If
-
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 returnans
. 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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
Sort the Array: We start by sorting
nums
, resulting in[-4, -1, -1, 0, 1, 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
, wheren
is the length of the sorted nums array. -
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 ton - 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.
-
Two-Pointer Technique: We start the two-pointer process with
i
,j
, andk
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 at2
(the last element).
-
Find the Triplets: In the while loop, we find sums of
nums[i] + nums[j] + nums[k]
and adjustj
andk
accordingly:- The first sum is
-4 + -1 + 2 = -3
, which is less than zero. We incrementj
to move to the next larger number, which is another-1
. - Now, the sum is
-4 + -1 + 2 = -3
, still less than zero. We incrementj
again and move to0
. - With
j
on0
, the sum is-4 + 0 + 2 = -2
, and we continue incrementingj
to move to1
. - The sum is now
-4 + 1 + 2 = -1
, which is still less than zero, so we movej
again, but now we've reached the end, and the while loop ends for thisi
.
- The first sum is
Next, with i = 1
, we find:
i = 1
(but this is skipped because it's the same asi = 0
).i = 2
, we have the first element as-1
,j = 3
andk = 5
, so we test the combination-1 + 0 + 2
, which sums to1
. The sum is greater than zero, so we decrementk
.- Now,
k
is4
, andj
is3
, so we test-1 + 0 + 1
, which sums to0
. 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.
- 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.
Solution Implementation
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
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
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
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
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 using problem constraints.
Problem: Given a list of tasks and a list of requirements, compute a sequence of tasks that can be performed, such that we complete every task once while satisfying all the requirements.
Which of the following method should we use to solve this problem?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Don’t Miss This!