3Sum
MedPrompt
Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
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-105 <= nums[i] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach iterates through every possible combination of three numbers in the array to check if their sum is zero. To handle duplicate triplets, the found triplets are sorted and stored in a Set.
Algorithm
-
- Initialize an empty
HashSetcalledresultSetto store unique triplets.
- Initialize an empty
-
- Use three nested loops to iterate through all unique combinations of indices
(i, j, k).
- Use three nested loops to iterate through all unique combinations of indices
-
- For each combination, check if
nums[i] + nums[j] + nums[k] == 0.
- For each combination, check if
-
- If the sum is zero, create a list with these three numbers.
-
- Sort the list to create a canonical representation of the triplet.
-
- Add the sorted list to the
resultSet.
- Add the sorted list to the
-
- After the loops complete, convert the
resultSetto anArrayListand return it.
- After the loops complete, convert the
Walkthrough
The most straightforward solution is to check every possible triplet in the array. We can achieve this using three nested loops. The outer loop iterates from i = 0 to n-3, the second loop from j = i + 1 to n-2, and the inner loop from k = j + 1 to n-1. Inside the innermost loop, we check if nums[i] + nums[j] + nums[k] == 0. A key challenge is avoiding duplicate triplets in the output. For example, [-1, 0, 1] and [0, 1, -1] represent the same triplet. To solve this, whenever we find a valid triplet, we sort it to have a canonical representation. Then, we add this sorted triplet to a HashSet to automatically filter out duplicates. Finally, we convert the HashSet of triplets into a List to return.
import java.util.*; class Solution { public List<List<Integer>> threeSum(int[] nums) { Set<List<Integer>> resultSet = new HashSet<>(); int n = nums.length; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { for (int k = j + 1; k < n; k++) { if (nums[i] + nums[j] + nums[k] == 0) { List<Integer> triplet = Arrays.asList(nums[i], nums[j], nums[k]); Collections.sort(triplet); resultSet.add(triplet); } } } } return new ArrayList<>(resultSet); }}Complexity
Time
O(n^3)
Space
O(k), where k is the number of unique triplets. In the worst case, this can be O(n^2).
Trade-offs
Pros
Simple to understand and implement.
Cons
Very inefficient, with a cubic time complexity.
Will likely result in a 'Time Limit Exceeded' error on most platforms for larger inputs.
This approach improves upon the brute-force method by reducing one loop. It iterates through the array, fixing one number nums[i], and then tries to find two other numbers that sum up to -nums[i]. This '2Sum' subproblem is solved efficiently using a hash set.
Algorithm
-
- Initialize an empty
HashSetcalledresultSetto store the unique result triplets.
- Initialize an empty
-
- Sort the input array
nums. This helps in skipping duplicates.
- Sort the input array
-
- Iterate through the array with an index
ifrom0ton-1.
- Iterate through the array with an index
-
- To avoid duplicate triplets, if
i > 0andnums[i]is the same asnums[i-1], skip the current iteration.
- To avoid duplicate triplets, if
-
- For each
nums[i], create a newHashSetcalledseen.
- For each
-
- Iterate through the rest of the array with an index
jfromi+1ton-1.
- Iterate through the rest of the array with an index
-
- Calculate the required third number:
complement = -nums[i] - nums[j].
- Calculate the required third number:
-
- If
seencontainscomplement, a triplet is found. Add(nums[i], nums[j], complement)to theresultSet.
- If
-
- Add
nums[j]to theseenset.
- Add
-
- After the loops, convert the
resultSetto aListand return it.
- After the loops, convert the
Walkthrough
We can optimize the O(n^3) approach to O(n^2) by using a hash set. The idea is to transform the problem into a series of 2Sum problems. We iterate through the array with a single loop, fixing the first element of the potential triplet, nums[i]. For each nums[i], the problem becomes: find two numbers in the rest of the array (nums[i+1] to nums[n-1]) that sum to target = -nums[i]. We can solve this 2Sum problem in O(n) time. For each nums[i], we iterate through the rest of the array with a second pointer j. We use a HashSet to store the numbers we've seen so far in this inner loop. For each nums[j], we calculate the complement = target - nums[j]. If the complement is already in our hash set, we've found a triplet. To avoid duplicate triplets, we can sort the input array first. This helps in skipping over duplicate values for nums[i]. Then we can store the resulting triplets in a Set to handle all other duplicate cases.
import java.util.*; class Solution { public List<List<Integer>> threeSum(int[] nums) { Set<List<Integer>> resultSet = new HashSet<>(); if (nums.length < 3) return new ArrayList<>(); Arrays.sort(nums); // Sort to handle duplicates easily for (int i = 0; i < nums.length - 2; i++) { // Skip duplicate elements for the first number if (i > 0 && nums[i] == nums[i-1]) { continue; } Set<Integer> seen = new HashSet<>(); for (int j = i + 1; j < nums.length; j++) { int complement = -nums[i] - nums[j]; if (seen.contains(complement)) { resultSet.add(Arrays.asList(nums[i], complement, nums[j])); } seen.add(nums[j]); } } return new ArrayList<>(resultSet); }}Complexity
Time
O(n^2)
Space
O(n) for the hash set used to solve the 2Sum subproblem.
Trade-offs
Pros
Significantly faster than the brute-force approach.
Relatively easy to reason about by breaking it down into a 2Sum problem.
Cons
Requires extra space for the hash set.
Can be slightly slower in practice than the two-pointer approach due to hash set overhead.
This is the most optimal and common approach. It involves sorting the array first and then using a two-pointer technique. For each element nums[i], two pointers (left and right) are used to scan the rest of the array to find two numbers that sum up to -nums[i]. Sorting allows for both efficient scanning and easy handling of duplicates.
Algorithm
-
- Initialize an empty
Listcalledresult.
- Initialize an empty
-
- Sort the input array
nums.
- Sort the input array
-
- Iterate through the sorted array with an index
ifrom0ton-3.
- Iterate through the sorted array with an index
-
- If
i > 0andnums[i] == nums[i-1], continue to the next iteration to avoid duplicate first elements.
- If
-
- Initialize two pointers:
left = i + 1andright = n - 1.
- Initialize two pointers:
-
- Set the
targetsum for the two pointers as-nums[i].
- Set the
-
- While
left < right:
- a. Calculate
sum = nums[left] + nums[right]. - b. If
sum == target, a triplet is found. Add(nums[i], nums[left], nums[right])toresult. - c. After finding a triplet, increment
leftand decrementright. Also, skip any subsequent duplicate elements forleftandrightto avoid duplicate triplets. - d. If
sum < target, incrementleftto increase the sum. - e. If
sum > target, decrementrightto decrease the sum.
- While
-
- Return the
resultlist.
- Return the
Walkthrough
This method combines sorting with the two-pointer technique to achieve an efficient O(n^2) solution with minimal space overhead. First, the input array nums is sorted in non-decreasing order. This takes O(n log n) time. We then iterate through the array with a for loop, fixing the first element of the triplet, nums[i]. For each nums[i], we initialize two pointers: left = i + 1 and right = n - 1. We then move these pointers inward until left crosses right, searching for a pair (nums[left], nums[right]) that sums to target = -nums[i]. Inside the while (left < right) loop, if nums[left] + nums[right] == target, we've found a valid triplet. If the sum is less than the target, we increment left; if it's greater, we decrement right. Duplicate handling is crucial and is handled efficiently by skipping over identical elements for nums[i] and for nums[left] and nums[right] after a triplet is found.
import java.util.*; class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList<>(); if (nums == null || nums.length < 3) { return result; } Arrays.sort(nums); for (int i = 0; i < nums.length - 2; i++) { // Skip duplicate elements for the first number if (i > 0 && nums[i] == nums[i - 1]) { continue; } int left = i + 1; int right = nums.length - 1; int target = -nums[i]; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) { result.add(Arrays.asList(nums[i], nums[left], nums[right])); // Skip duplicate elements for the second number while (left < right && nums[left] == nums[left + 1]) { left++; } // Skip duplicate elements for the third number while (left < right && nums[right] == nums[right - 1]) { right--; } left++; right--; } else if (sum < target) { left++; } else { // sum > target right--; } } } return result; }}Complexity
Time
O(n^2). The O(n log n) sorting time is dominated by the O(n^2) two-pointer scan.
Space
O(log n) or O(n), depending on the sorting algorithm's implementation. This does not include the space required for the output list.
Trade-offs
Pros
Most efficient time complexity.
Low auxiliary space complexity.
Handles duplicates elegantly without needing an extra data structure like a
HashSetfor the results.
Cons
Requires modifying the input array by sorting it. If the original order must be preserved, a copy should be made first.
Solutions
Solution
public class Solution { public IList < IList < int >> ThreeSum(int[] nums) { Array.Sort(nums); int n = nums.Length; IList < IList < int >> ans = new List < IList < int >> (); for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.Add(new List < int > { nums[i], nums[j--], nums[k--] }); while (j < k && nums[j] == nums[j + 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; }}class Solution {public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> ans = new ArrayList<>(); int n = nums.length; for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i > 0 && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.add(List.of(nums[i], nums[j++], nums[k--])); while (j < k && nums[j] == nums[j - 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; }}/** * @param {number[]} nums * @return {number[][]} */ var threeSum = function ( nums ) { const n = nums . length ; nums . sort (( a , b ) => a - b ); const ans = []; for ( let i = 0 ; i < n - 2 && nums [ i ] <= 0 ; ++ i ) { if ( i > 0 && nums [ i ] === nums [ i - 1 ]) { continue ; } let j = i + 1 ; let k = n - 1 ; while ( j < k ) { const x = nums [ i ] + nums [ j ] + nums [ k ]; if ( x < 0 ) { ++ j ; } else if ( x > 0 ) { -- k ; } else { ans . push ([ nums [ i ], nums [ j ++ ], nums [ k -- ]]); while ( j < k && nums [ j ] === nums [ j - 1 ]) { ++ j ; } while ( j < k && nums [ k ] === nums [ k + 1 ]) { -- k ; } } } } return ans ; };class Solution {public: vector<vector<int>> threeSum(vector<int> &nums) { sort(nums.begin(), nums.end()); vector<vector<int>> ans; int n = nums.size(); for (int i = 0; i < n - 2 && nums[i] <= 0; ++i) { if (i && nums[i] == nums[i - 1]) { continue; } int j = i + 1, k = n - 1; while (j < k) { int x = nums[i] + nums[j] + nums[k]; if (x < 0) { ++j; } else if (x > 0) { --k; } else { ans.push_back({nums[i], nums[j++], nums[k--]}); while (j < k && nums[j] == nums[j - 1]) { ++j; } while (j < k && nums[k] == nums[k + 1]) { --k; } } } } return ans; }};class Solution: def threeSum(self, nums: List[int]) -> List[List[int]]: nums . sort() n = len(nums) ans = [] for i in range(n - 2): if nums[i] > 0: break if i and nums[i] == nums[i - 1]: continue j, k = i + 1, n - 1 while j < k: x = nums[i] + nums[j] + nums[k] if x < 0: j += 1 elif x > 0: k -= 1 else: ans . append([nums[i], nums[j], nums[k]]) j, k = j + 1, k - 1 while j < k and nums[j] == nums[j - 1]: j += 1 while j < k and nums[k] == nums[k + 1]: k -= 1 return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.