3Sum
Find list of unique triplets that sum up to zero.
Medium
Difficulty
O(n^2)
Time Complexity
O(1)
Space Complexity
Sorting, Binary Search
Approach
Jan 18, 2026
Last Updated
Problem Statement
Given an integer array
nums, return all the triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] == 0, and the indices i, j and k are all distinct.
The output should not contain any duplicate triplets. You may return the output and the triplets in any order.Examples
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].
Example 2:
Input: [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.
Mathematical Approach
We need to find triplets that sum up to zero, say , and .
Then,
This now becomes the 2 sum problem. With target as .
Using 2 Sum approach with HashMap
We can solve this problem using the 2 sum approach of hashmaps, looping through the array, setting the target as
-nums[i] and then creating a hashmap that stores the complements to look for them later.
Complexity Analysis
Time Complexity
HashMap: O(n^2)
Space Complexity
HashMap: O(n)
Sorting and Binary Search
The optimal solution would be a mix of sorting and binary search approaches. Although, it doesn't save much on time, but we can avoid the space complexity and make the solution use O(1) auxiliary space.
Sorting and Binary Search
3SumOptimal.javaSorting and Binary Search
1class Solution {
2 public List<List<Integer>> 3SumOptimal(int[] nums) {
3
4 Arrays.sort(nums);
5
6 List<List<Integer>> finalList = new ArrayList<>();
7 if (nums.length < 3) return finalList;
8
9 int target, low, high, sum;
10
11 for (int i=0; i<nums.length; i++){
12
13 if (i>0 && nums[i] == nums[i-1])
14 continue;
15
16 target = (-1)*nums[i];
17 low = i+1;
18 high = nums.length-1;
19 while (low < high){
20 sum = nums[low] + nums[high];
21 if (sum == target){
22 List<Integer> list = new ArrayList<>();
23 list.add(nums[i]);
24 list.add(nums[low]);
25 list.add(nums[high]);
26 finalList.add(list);
27
28 // skip duplicate low and high values
29 while (low+1 < nums.length && nums[low] == nums[low+1]){
30 low++;
31 }
32 while (high-1 >= 0 && nums[high] == nums[high-1]){
33 high--;
34 }
35 low++;
36 high--;
37 }
38 else if (sum < target){
39 low++;
40 }
41 else {
42 high--;
43 }
44 }
45 }
46
47 return finalList;
48 }
49}
50Complexity Analysis
Time Complexity
Sorting & Binary Search: O(n^2)
Space Complexity
Sorting & Binary Search: O(1)
Step-by-Step Walkthrough
1
We start by sorting the array
2
If our array already contains less than 3 items, which is not enough to create triplets, we directly return
3
We loop through the array, using index i
4
if we want triplets with nums[i], our target for the remaining 2 items would be -nums[i]
5
Now we use binary search to search for the remaining 2 elements that sum up to -nums[i]
6
we take pointers low and high. sum = nums[low]+nums[high]
7
if sum < target, we increment low. If sum > target, we decrement high
8
If we find sum == target, we found a triplet. We create a list with the 3 numbers and add to our final list
9
Since duplicates are not allowed, we skip low up till nums[low] is found to be a new item
10
similarly, we skip high down up till nums[high] is found to be a new item
11
In case the immediate next low and high index values were already unique, the skip wont work. So we need to manually increment/decrement them so as to move to the next combination
12
We also need to skip i to find a new unique target value to avoid duplicates
13
Once we've found all the triplets, we return the final list