3Sum
Problem
Given an integer array nums, return all unique triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.
- 0 ≤ nums.length ≤ 3000
- −10⁵ ≤ nums[i] ≤ 10⁵
Example
nums = [-1,0,1,2,-1,-4][[-1,-1,2],[-1,0,1]]First, the array is sorted to [-4,-1,-1,0,1,2]. The algorithm iterates through each number as a potential first element of the triplet. At index 1 (value -1), it uses two pointers starting at indices 2 and 5 to find pairs that sum with -1 to zero. The pair (nums[2], nums[5]) = (-1, 2) sums to 1, so the right pointer moves left. Eventually, the pair (-1, 2) is found, forming the triplet [-1, -1, 2]. The algorithm skips duplicates by checking if the current number equals the previous one. This process continues, finding the second triplet [-1, 0, 1]. The key is sorting and skipping duplicates to avoid repeated triplets.
Approach
Straightforward Solution
A brute-force approach would check all triplets with three nested loops, resulting in O(n^3) time complexity, which is too slow for large inputs.
Core Observation
The problem requires finding triplets that sum to zero without duplicates. Sorting the array enables efficient two-pointer scanning for pairs that complement the current element to zero, and also allows easy skipping of duplicates to ensure unique triplets.
Path to Optimal
Sorting the array allows fixing one element and searching for the other two using two pointers moving inward from both ends of the remaining array. This reduces the complexity to O(n^2). Skipping duplicates at both the fixed element and during pointer movement prevents repeated triplets.
Optimal Approach
Sort the array. Iterate through each element as the first element of the triplet, skipping duplicates. For each fixed element, use two pointers (left and right) to find pairs that sum to the negative of the fixed element. Move pointers inward based on the sum comparison, skipping duplicates to avoid repeated triplets. Collect all valid triplets in the result list.
Time
O(n^2)
Sorting takes O(n log n). The main loop runs O(n) times, and for each iteration, the two-pointer search runs in O(n), resulting in O(n^2) overall.
Space
O(n)
The sorting algorithm requires O(n) space in the worst case. The output list space is not counted as auxiliary space.
Pattern Spotlight
Two Pointers (Sorted Array Pair Search)
When searching for pairs that sum to a target in a sorted array, use two pointers starting at opposite ends and move inward based on the sum comparison; this approach efficiently finds all pairs in O(n) time and can be extended to triplets by fixing one element and searching pairs for the complement.
Solution
| 1 | class Solution:
|
| 2 | def threeSum(self, nums: list[int]) -> list[list[int]]:
|
| 3 | res = []
|
| 4 | nums.sort()
|
| 5 |
|
| 6 | for i, a in enumerate(nums):
|
| 7 | if i > 0 and a == nums[i - 1]:
|
| 8 | continue
|
| 9 |
|
| 10 | l, r = i + 1, len(nums) - 1
|
| 11 | while l < r:
|
| 12 | three_sum = a + nums[l] + nums[r]
|
| 13 | if three_sum > 0:
|
| 14 | r -= 1
|
| 15 | elif three_sum < 0:
|
| 16 | l += 1
|
| 17 | else:
|
| 18 | res.append([a, nums[l], nums[r]])
|
| 19 | l += 1
|
| 20 | while l < r and nums[l] == nums[l - 1]:
|
| 21 | l += 1
|
| 22 | return res |
| 1 | import java.util.ArrayList; |
| 2 | import java.util.Arrays; |
| 3 | import java.util.List; |
| 4 | |
| 5 | class Solution { |
| 6 | public List<List<Integer>> threeSum(int[] nums) { |
| 7 | List<List<Integer>> res = new ArrayList<>(); |
| 8 | Arrays.sort(nums); |
| 9 | |
| 10 | for (int i = 0; i < nums.length; i++) { |
| 11 | int a = nums[i]; |
| 12 | if (i > 0 && a == nums[i - 1]) { |
| 13 | continue; |
| 14 | } |
| 15 | |
| 16 | int l = i + 1; |
| 17 | int r = nums.length - 1; |
| 18 | while (l < r) { |
| 19 | int threeSum = a + nums[l] + nums[r]; |
| 20 | if (threeSum > 0) { |
| 21 | r--; |
| 22 | } else if (threeSum < 0) { |
| 23 | l++; |
| 24 | } else { |
| 25 | res.add(Arrays.asList(a, nums[l], nums[r])); |
| 26 | l++; |
| 27 | while (l < r && nums[l] == nums[l - 1]) { |
| 28 | l++; |
| 29 | } |
| 30 | } |
| 31 | } |
| 32 | } |
| 33 | |
| 34 | return res; |
| 35 | } |
| 36 | } |
| 1 | #include <vector> |
| 2 | #include <algorithm> |
| 3 | |
| 4 | using namespace std; |
| 5 | |
| 6 | class Solution { |
| 7 | public: |
| 8 | vector<vector<int>> threeSum(vector<int>& nums) { |
| 9 | vector<vector<int>> res; |
| 10 | sort(nums.begin(), nums.end()); |
| 11 | |
| 12 | for (int i = 0; i < (int)nums.size(); i++) { |
| 13 | int a = nums[i]; |
| 14 | if (i > 0 && a == nums[i - 1]) { |
| 15 | continue; |
| 16 | } |
| 17 | |
| 18 | int l = i + 1; |
| 19 | int r = (int)nums.size() - 1; |
| 20 | while (l < r) { |
| 21 | int threeSum = a + nums[l] + nums[r]; |
| 22 | if (threeSum > 0) { |
| 23 | r--; |
| 24 | } else if (threeSum < 0) { |
| 25 | l++; |
| 26 | } else { |
| 27 | res.push_back({a, nums[l], nums[r]}); |
| 28 | l++; |
| 29 | while (l < r && nums[l] == nums[l - 1]) { |
| 30 | l++; |
| 31 | } |
| 32 | } |
| 33 | } |
| 34 | } |
| 35 | |
| 36 | return res; |
| 37 | } |
| 38 | }; |
| 1 | var threeSum = function(nums) { |
| 2 | const res = []; |
| 3 | nums.sort((a, b) => a - b); |
| 4 | |
| 5 | for (let i = 0; i < nums.length; i++) { |
| 6 | const a = nums[i]; |
| 7 | if (i > 0 && a === nums[i - 1]) { |
| 8 | continue; |
| 9 | } |
| 10 | |
| 11 | let l = i + 1; |
| 12 | let r = nums.length - 1; |
| 13 | while (l < r) { |
| 14 | const threeSum = a + nums[l] + nums[r]; |
| 15 | if (threeSum > 0) { |
| 16 | r--; |
| 17 | } else if (threeSum < 0) { |
| 18 | l++; |
| 19 | } else { |
| 20 | res.push([a, nums[l], nums[r]]); |
| 21 | l++; |
| 22 | while (l < r && nums[l] === nums[l - 1]) { |
| 23 | l++; |
| 24 | } |
| 25 | } |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | return res; |
| 30 | }; |
Step-by-Step Solution
Sort the Array and Initialize Result Container
| 3 | res = []
|
| 4 | nums.sort()
|
Objective
To prepare the input for efficient two-pointer searching and store the resulting triplets.
Key Insight
Sorting the array is essential because it enables the two-pointer technique to find pairs summing to a target in linear time. Initializing the result list upfront provides a container to accumulate valid triplets.
Interview Quick-Check
Core Logic
Sorting transforms the problem into a structured search space where two pointers can efficiently find pairs summing to a target.
State & Boundaries
The result list must be initialized before iteration to collect all valid triplets.
Iterate Over Array, Skipping Duplicate Fixed Elements
| 6 | for i, a in enumerate(nums):
|
| 7 | if i > 0 and a == nums[i - 1]:
|
| 8 | continue
|
Objective
To select each unique element as the first element of potential triplets while avoiding duplicate work.
Key Insight
By skipping fixed elements that are the same as the previous one, the algorithm avoids generating duplicate triplets starting with the same number. This pruning is critical to ensure uniqueness and reduce unnecessary computations.
Interview Quick-Check
Core Logic
Skipping duplicates at the fixed element level prevents repeated triplets that differ only in order.
Common Pitfalls & Bugs
Failing to skip duplicates here leads to duplicate triplets in the output.
Use Two Pointers to Find Complementary Pairs for Each Fixed Element
| 10 | l, r = i + 1, len(nums) - 1
|
| 11 | while l < r:
|
| 12 | three_sum = a + nums[l] + nums[r]
|
| 13 | if three_sum > 0:
|
| 14 | r -= 1
|
| 15 | elif three_sum < 0:
|
| 16 | l += 1
|
| 17 | else:
|
| 18 | res.append([a, nums[l], nums[r]])
|
| 19 | l += 1
|
| 20 | while l < r and nums[l] == nums[l - 1]:
|
| 21 | l += 1
|
Objective
To find all pairs in the remaining array that sum with the fixed element to zero, efficiently and without duplicates.
Key Insight
The two-pointer technique exploits the sorted order to move pointers inward based on the sum comparison, eliminating the need for nested loops. After finding a valid triplet, advancing the left pointer and skipping duplicates ensures unique triplets are collected without redundant checks.
Interview Quick-Check
Core Logic
Two pointers scan from both ends towards the center, adjusting based on the sum relative to zero, to find all valid pairs in O(n) time.
State & Boundaries
The loop continues while left pointer is less than right pointer, ensuring pairs are unique and no invalid indices are accessed.
Common Pitfalls & Bugs
Not skipping duplicates after finding a valid triplet causes repeated triplets in the result.
Complexity
This approach reduces the pair search from O(n^2) to O(n) per fixed element, leading to O(n^2) overall.
Return the List of Unique Triplets
| 22 | return res |
Objective
To output the final collection of all unique triplets found.
Key Insight
After completing the iteration and pair searches, the result list contains all valid triplets without duplicates, ready to be returned as the solution.
Interview Quick-Check
Core Logic
Returning the accumulated result completes the algorithm and provides the answer to the problem.
Line Analysis
This solution has 3 Critical lines interviewers watch for.
if i > 0 and a == nums[i - 1]:Skip the current element if it is the same as the previous to avoid duplicates.
Skipping duplicates at the fixed element prevents generating identical triplets multiple times, ensuring uniqueness in the result.
else:If the sum equals zero, a valid triplet is found.
This condition identifies the core success case where the three numbers sum to zero, ready to be recorded.
while l < r and nums[l] == nums[l - 1]:Skip duplicate elements at the left pointer to avoid repeated triplets.
This loop prevents adding triplets with the same second element multiple times, ensuring uniqueness.
nums.sort()Sort the input array in ascending order.
Sorting enables the two-pointer technique by imposing order, which allows efficient pair searching and duplicate skipping.
if three_sum > 0:If the sum is greater than zero, move the right pointer left to reduce sum.
Because the array is sorted, decreasing the right pointer moves to a smaller number, reducing the sum towards zero.
elif three_sum < 0:If the sum is less than zero, move the left pointer right to increase sum.
Increasing the left pointer moves to a larger number, increasing the sum towards zero in a sorted array.
continueContinue to the next iteration if duplicate fixed element detected.
This control flow enforces the duplicate skipping logic, preventing redundant computations.
l, r = i + 1, len(nums) - 1Initialize two pointers: left just after fixed element, right at array end.
Setting pointers at these positions prepares for scanning the remaining array for pairs that complement the fixed element to zero.
three_sum = a + nums[l] + nums[r]Calculate the sum of the fixed element and the two pointers' elements.
This sum determines whether the current triplet meets the zero-sum condition or if pointers need adjustment.
res.append([a, nums[l], nums[r]])Append the found triplet to the result list.
Recording the valid triplet ensures it is included in the final output.
l += 1Move the left pointer right to continue searching for other pairs.
Advancing the left pointer explores new pairs while avoiding duplicates of the current left element.
while l < r:Loop while left pointer is less than right pointer.
This condition ensures valid pairs are considered and terminates when pointers cross, completing the search for the current fixed element.
l += 1Increment the left pointer while duplicates are found.
This enforces the duplicate skipping logic after a valid triplet is recorded.
for i, a in enumerate(nums):Iterate over the array with index and value.
This loop selects each element as a potential first element of a triplet, setting up the two-pointer search for the other two elements.
r -= 1Decrement the right pointer.
This action implements the strategy to reduce the sum by moving to a smaller number on the right side.
l += 1Increment the left pointer.
This action implements the strategy to increase the sum by moving to a larger number on the left side.
return resReturn the list of all unique triplets found.
This completes the algorithm by outputting the accumulated valid triplets as the solution.
res = []Initialize an empty list to store the resulting triplets.
This list accumulates all unique triplets found during the search, serving as the output container.
Test Your Understanding
Why is it necessary to skip duplicates both when fixing the first element and when moving the left pointer?
Skipping duplicates prevents generating identical triplets multiple times. For the fixed element, it avoids repeating the same starting point. For the left pointer, it avoids including the same pair multiple times, ensuring the result contains unique triplets.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct 3Sum from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the 3Sum drill