15% off all plans & roadmaps Use code
See plans3Sum
- LeetCode 15
- Medium
- Two Pointers
- Converging (Sorted Array Target Sum)
Updated
TL;DR: Find every unique triplet in an array that sums to zero. Sort the array, fix one number, and close in on the other two with converging pointers. Skip repeated values so no triplet appears twice.
Problem
Given an integer array nums, return all triplets [nums[i], nums[j], nums[k]] where i, j, and k are all different indices and nums[i] + nums[j] + nums[k] == 0.
The answer must not contain the same triplet twice. The order of the triplets, and the order of the numbers inside a triplet, does not matter.
Example 1
Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] Explanation: (-1) + 0 + 1 = 0, 0 + 1 + (-1) = 0, and (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].
Example 2
Input: nums = [0,1,1] Output: [] Explanation: The only possible triplet does not sum to 0.
Example 3
Input: nums = [0,0,0] Output: [[0,0,0]] Explanation: The only possible triplet sums to 0.
Constraints
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Constraints that matter
- n up to 3000 rules out O(n^3) in the worst case: that is about 4.5 billion triples to check (n choose 3), far too many for a time limit.
- n up to 3000 makes O(n^2) fine: about 9 million steps, which runs well within a second in every language.
- Values fall within -10^5 to 10^5, so a sum of three values is at most 3 * 10^5 in size. No integer overflow is possible, even in Java or C#.
- The answer must contain no duplicate triplets, and the input can hold many repeated values. You need a plan for uniqueness, not only for finding sums.
- The order of the output does not matter, so you are free to sort the input first.
Hints
Hint 1
This is a two pointers problem hiding behind a three-number sum.
Hint 2
Try every group of three indices i < j < k and keep the ones that sum to zero.
Solution
Intuition
This is a two pointers problem hiding behind a three-number sum. If you fix one number a, you need two other numbers that add up to -a. That is Two Sum with a target, and Two Sum on a sorted array has a clean answer with a pointer at each end.
Picture a sorted row of price tags with one shopper at each end. If the total is too low, the left shopper steps to a bigger tag. If it is too high, the right shopper steps to a smaller one, so each step throws away a tag that cannot work.
Sorting makes the pointer moves safe. If the current sum is too small, only moving the left pointer right can raise it. If the sum is too big, only moving the right pointer left can lower it. Neither move can skip a valid pair.
Sorting also puts equal values next to each other. The problem asks for unique triplets, so you must avoid reusing the same value in the same role. After sorting, you compare a value with its neighbour and skip when they match. You need no set of triplets at all.
The cost is one sort, O(n log n), plus one pointer sweep per fixed number, O(n) each. The total is O(n^2), which is the best known bound for general 3Sum. Remember the pattern: sort, fix one, converge two.
Worked example
Input: nums = [-3, -2, -1, 0, 1, 2, 3] Output: [[-3, 0, 3], [-3, 1, 2], [-2, -1, 3], [-2, 0, 2], [-1, 0, 1]] Explanation: The array is already sorted and has no repeated values. Of the 35 possible triplets, exactly five sum to zero: -3+0+3, -3+1+2, -2+-1+3, -2+0+2 and -1+0+1. Every other choice of three values gives a positive or negative total.
Approach 1: Brute force with a set
Try every group of three indices i < j < k and keep the ones that sum to zero. To avoid duplicates, sort the array first so equal triplets look identical, then store each found triplet in a set. Only triplets not yet in the set go into the answer.
This is correct and needs no insight. It is also slow, because it examines every triple even when most of them can never work.
Steps
- Copy and sort the array so every triplet is written in ascending order.
- Loop
ifrom 0 to n-1. - Loop
jfromi + 1to n-1. - Loop
kfromj + 1to n-1. - If
nums[i] + nums[j] + nums[k] == 0, build the triplet as a key. - If the key is not in the seen set, add it to the set and to the result.
- Return the result.
Dry run
Sorted input: [-3,-2,-1,0,1,2,3], so n = 7 and there are 35 index triples.
(-3,-2,-1)sums to -6, skip.(-3,-2,0)sums to -5, skip. This continues for every triple that starts with -3.(-3,0,3)sums to 0. It is new, so it goes into the result.(-3,1,2)sums to 0. New, added.- Starting with -2:
(-2,-1,3)and(-2,0,2)both sum to 0 and are added. - Starting with -1:
(-1,0,1)sums to 0 and is added. - Every other triple has a nonzero sum.
All 35 triples were checked, and the result is [[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,0,1]].
Complexity
| Time | O(n^3) |
|---|---|
| Space | O(n) |
Here n is the array length. The three nested loops visit n choose 3 triples, which grows as n^3 / 6, so time is O(n^3). The sorted copy takes O(n) space. The seen set holds at most one entry per distinct answer triplet, which can reach O(n^2) entries in the worst case. For n = 3000 the loops make around 4.5 billion checks, so the solution times out.
PythonTested in our runner
from typing import List, Optional
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
n = len(nums)
seen = set()
result = []
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if nums[i] + nums[j] + nums[k] == 0:
t = (nums[i], nums[j], nums[k])
if t not in seen:
seen.add(t)
result.append(list(t))
return result
JavaTested in our runner
import java.util.*;
class Solution {
public int[][] threeSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
Set<String> seen = new HashSet<>();
List<int[]> res = new ArrayList<>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
String key = a[i] + "," + a[j] + "," + a[k];
if (seen.add(key)) {
res.add(new int[]{a[i], a[j], a[k]});
}
}
}
}
}
return res.toArray(new int[0][]);
}
};
C++Tested in our runner
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = a.size();
set<vector<int>> seen;
vector<vector<int>> result;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
vector<int> t = {a[i], a[j], a[k]};
if (seen.insert(t).second) {
result.push_back(t);
}
}
}
}
}
return result;
}
};
JavaScriptTested in our runner
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const a = [...nums].sort((x, y) => x - y);
const n = a.length;
const seen = new Set();
const result = [];
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] === 0) {
const key = `${a[i]},${a[j]},${a[k]}`;
if (!seen.has(key)) {
seen.add(key);
result.push([a[i], a[j], a[k]]);
}
}
}
}
}
return result;
};
GoTested in our runner
import "sort"
func threeSum(nums []int) [][]int {
a := append([]int(nil), nums...)
sort.Ints(a)
n := len(a)
seen := map[[3]int]bool{}
result := [][]int{}
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if a[i]+a[j]+a[k] == 0 {
key := [3]int{a[i], a[j], a[k]}
if !seen[key] {
seen[key] = true
result = append(result, []int{a[i], a[j], a[k]})
}
}
}
}
}
return result
}
C#Tested in our runner
public class Solution {
public int[][] threeSum(int[] nums) {
int[] a = (int[])nums.Clone();
Array.Sort(a);
int n = a.Length;
var seen = new HashSet<string>();
var res = new List<int[]>();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (a[i] + a[j] + a[k] == 0) {
string key = a[i] + "," + a[j] + "," + a[k];
if (seen.Add(key)) {
res.Add(new int[] { a[i], a[j], a[k] });
}
}
}
}
}
return res.ToArray();
}
}
Approach 2: Sort, then hash map lookup
What's slow: the innermost loop re-scans the array to find a third number that the first two already determine. Given a and b, the third value must be -a - b. Searching for it linearly wastes O(n) work per pair.
The insight that fixes it: replace that scan with a hash map lookup. Sort the array, then store each value's last index in a map. For each pair (i, j), compute c = -a - b and check whether c appears at an index greater than j. Skipping repeated values for i and j keeps triplets unique without a set.
Steps
- Sort the array.
- Build a map from each value to its last index in the sorted array.
- Loop
ifrom 0 to n-3, skipping it whennums[i] == nums[i-1]. - Loop
jfromi + 1to n-2, skipping it whenj > i + 1andnums[j] == nums[j-1]. - Compute
c = -nums[i] - nums[j]. - If the map has
cwith last index greater thanj, record[nums[i], nums[j], c]. - Return the result.
Dry run
Sorted input: [-3,-2,-1,0,1,2,3]. The map sends each value to its index, for example -3 -> 0 and 3 -> 6.
i = 0(a = -3):j = 1gives c = 5, missing.j = 2gives c = 4, missing.j = 3(b = 0) gives c = 3 at index 6 > 3, so record[-3,0,3].j = 4(b = 1) gives c = 2 at index 5 > 4, so record[-3,1,2].j = 5gives c = 1 at index 4, not greater than 5.j = 6is out of range for the inner loop.i = 1(a = -2):j = 2(b = -1) gives c = 3, record[-2,-1,3].j = 3(b = 0) gives c = 2 at index 5 > 3, record[-2,0,2].j = 4gives c = 1 at index 4, not greater than 4.j = 5gives c = 0 at index 3, rejected.i = 2(a = -1):j = 3(b = 0) gives c = 1 at index 4 > 3, record[-1,0,1].j = 4gives c = 0 at index 3, rejected.j = 5gives c = -1 at index 2, rejected.i = 3(a = 0): every c is negative or at a smaller index, so nothing is recorded.i = 4finds nothing either.
The result is the five expected triplets.
Complexity
| Time | O(n^2) |
|---|---|
| Space | O(n) |
Here n is the array length. Sorting costs O(n log n), building the map costs O(n), and the double loop runs at most n * n / 2 times with an O(1) average lookup each, so time is O(n^2). The map holds one entry per distinct value, so extra space is O(n), plus the sort. The last-index check guarantees the third number sits to the right of j, so the same element is never used twice.
PythonTested in our runner
from typing import List, Optional
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
n = len(nums)
# value -> last index where it appears
last = {v: i for i, v in enumerate(nums)}
result = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
c = -nums[i] - nums[j]
# the third value must sit to the right of j
if last.get(c, -1) > j:
result.append([nums[i], nums[j], c])
return result
JavaTested in our runner
import java.util.*;
class Solution {
public int[][] threeSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
Map<Integer, Integer> last = new HashMap<>();
for (int i = 0; i < n; i++) {
last.put(a[i], i);
}
List<int[]> res = new ArrayList<>();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < n - 1; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
int c = -a[i] - a[j];
if (last.getOrDefault(c, -1) > j) {
res.add(new int[]{a[i], a[j], c});
}
}
}
return res.toArray(new int[0][]);
}
};
C++Tested in our runner
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = a.size();
unordered_map<int, int> last;
for (int i = 0; i < n; i++) {
last[a[i]] = i;
}
vector<vector<int>> result;
for (int i = 0; i + 2 < n; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j + 1 < n; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
int c = -a[i] - a[j];
auto it = last.find(c);
if (it != last.end() && it->second > j) {
result.push_back({a[i], a[j], c});
}
}
}
return result;
}
};
JavaScriptTested in our runner
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const a = [...nums].sort((x, y) => x - y);
const n = a.length;
const last = new Map();
for (let i = 0; i < n; i++) {
last.set(a[i], i);
}
const result = [];
for (let i = 0; i < n - 2; i++) {
if (i > 0 && a[i] === a[i - 1]) continue;
for (let j = i + 1; j < n - 1; j++) {
if (j > i + 1 && a[j] === a[j - 1]) continue;
const c = -a[i] - a[j];
if (last.has(c) && last.get(c) > j) {
result.push([a[i], a[j], c]);
}
}
}
return result;
};
GoTested in our runner
import "sort"
func threeSum(nums []int) [][]int {
a := append([]int(nil), nums...)
sort.Ints(a)
n := len(a)
last := make(map[int]int)
for i, v := range a {
last[v] = i
}
result := [][]int{}
for i := 0; i < n-2; i++ {
if i > 0 && a[i] == a[i-1] {
continue
}
for j := i + 1; j < n-1; j++ {
if j > i+1 && a[j] == a[j-1] {
continue
}
c := -a[i] - a[j]
if idx, ok := last[c]; ok && idx > j {
result = append(result, []int{a[i], a[j], c})
}
}
}
return result
}
C#Tested in our runner
public class Solution {
public int[][] threeSum(int[] nums) {
int[] a = (int[])nums.Clone();
Array.Sort(a);
int n = a.Length;
var last = new Dictionary<int, int>();
for (int i = 0; i < n; i++) {
last[a[i]] = i;
}
var res = new List<int[]>();
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
for (int j = i + 1; j < n - 1; j++) {
if (j > i + 1 && a[j] == a[j - 1]) continue;
int c = -a[i] - a[j];
if (last.TryGetValue(c, out int idx) && idx > j) {
res.Add(new int[] { a[i], a[j], c });
}
}
}
return res.ToArray();
}
}

Solution pattern
Converging (Sorted Array Target Sum)
Part of Two Pointers
Approach 3: Sort, then converging two pointersOptimalConverging (Sorted Array Target Sum)
What's slow: the hash map approach still visits every pair (i, j) and pays for hashing and extra memory. For a fixed i, the sorted order already tells you which way to move, so you do not need to test every j.
The insight that fixes it: for each fixed i, put left at i + 1 and right at the end. If the sum is negative, increase left. If it is positive, decrease right. Each move discards a value that cannot be part of any answer with this i, so one sweep costs O(n) with no hashing. After a hit, skip equal neighbours to keep triplets unique.
Why it is correct. For a fixed i, every valid pair lies between left and right in the sorted array. If the sum is negative, nums[left] cannot reach zero with any value at or before right, since those values are no larger. The same argument removes right when the sum is positive, so the sweep finds every triplet for this i.
Steps
- Sort the array.
- Loop
ifrom 0 to n-3. Stop early ifnums[i] > 0, since all later values are positive too. - Skip
iwhennums[i] == nums[i-1]so the same first value is not used twice. - Set
left = i + 1andright = n - 1. - While
left < right, computetotal = nums[i] + nums[left] + nums[right]. - If
total < 0, moveleftright. Iftotal > 0, moverightleft. - If
total == 0, record the triplet, then moveleftpast all copies of its value andrightpast all copies of its value. - Return the result.
Dry run
Sorted input: [-3,-2,-1,0,1,2,3]. Each row shows the state before the move.
| i | nums[i] | left | right | nums[left] | nums[right] | total | action |
|---|---|---|---|---|---|---|---|
| 0 | -3 | 1 | 6 | -2 | 3 | -2 | too small, left++ |
| 0 | -3 | 2 | 6 | -1 | 3 | -1 | too small, left++ |
| 0 | -3 | 3 | 6 | 0 | 3 | 0 | record [-3,0,3], left=4, right=5 |
| 0 | -3 | 4 | 5 | 1 | 2 | 0 | record [-3,1,2], left=5, right=4 |
| 1 | -2 | 2 | 6 | -1 | 3 | 0 | record [-2,-1,3], left=3, right=5 |
| 1 | -2 | 3 | 5 | 0 | 2 | 0 | record [-2,0,2], left=4, right=4 |
| 2 | -1 | 3 | 6 | 0 | 3 | 2 | too big, right-- |
| 2 | -1 | 3 | 5 | 0 | 2 | 1 | too big, right-- |
| 2 | -1 | 3 | 4 | 0 | 1 | 0 | record [-1,0,1], left=4, right=3 |
| 3 | 0 | 4 | 6 | 1 | 3 | 4 | too big, right-- |
| 3 | 0 | 4 | 5 | 1 | 2 | 3 | too big, right-- |
| 4 | 1 | - | - | - | - | - | nums[i] > 0, stop |
The loop ends with [[-3,0,3],[-3,1,2],[-2,-1,3],[-2,0,2],[-1,0,1]].
Complexity
| Time | O(n^2) |
|---|---|
| Space | O(1) |
Here n is the array length. Sorting costs O(n log n). For each of the n values of i, left and right together move at most n steps before they meet, so the sweep is O(n) and the total is O(n^2). Besides the sort and the output list, you store only a few integers. Extra space is O(1) if the sort is in place, or O(log n) for the sort stack in some languages.
PythonTested in our runner
from typing import List, Optional
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums = sorted(nums)
n = len(nums)
result = []
for i in range(n - 2):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, n - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total < 0:
left += 1
elif total > 0:
right -= 1
else:
result.append([nums[i], nums[left], nums[right]])
# skip all copies of the values just used
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
return result
JavaTested in our runner
import java.util.*;
class Solution {
public int[][] threeSum(int[] nums) {
int[] a = nums.clone();
Arrays.sort(a);
int n = a.length;
List<int[]> res = new ArrayList<>();
for (int i = 0; i < n - 2; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] == a[i - 1]) continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int total = a[i] + a[left] + a[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
res.add(new int[]{a[i], a[left], a[right]});
while (left < right && a[left] == a[left + 1]) left++;
while (left < right && a[right] == a[right - 1]) right--;
left++;
right--;
}
}
}
return res.toArray(new int[0][]);
}
};
C++Tested in our runner
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = a.size();
vector<vector<int>> result;
for (int i = 0; i + 2 < n; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] == a[i - 1]) continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int total = a[i] + a[left] + a[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
result.push_back({a[i], a[left], a[right]});
while (left < right && a[left] == a[left + 1]) left++;
while (left < right && a[right] == a[right - 1]) right--;
left++;
right--;
}
}
}
return result;
}
};
JavaScriptTested in our runner
/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSum = function(nums) {
const a = [...nums].sort((x, y) => x - y);
const n = a.length;
const result = [];
for (let i = 0; i < n - 2; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] === a[i - 1]) continue;
let left = i + 1;
let right = n - 1;
while (left < right) {
const total = a[i] + a[left] + a[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
result.push([a[i], a[left], a[right]]);
while (left < right && a[left] === a[left + 1]) left++;
while (left < right && a[right] === a[right - 1]) right--;
left++;
right--;
}
}
}
return result;
};
GoTested in our runner
import "sort"
func threeSum(nums []int) [][]int {
a := append([]int(nil), nums...)
sort.Ints(a)
n := len(a)
result := [][]int{}
for i := 0; i < n-2; i++ {
if a[i] > 0 {
break
}
if i > 0 && a[i] == a[i-1] {
continue
}
left, right := i+1, n-1
for left < right {
total := a[i] + a[left] + a[right]
if total < 0 {
left++
} else if total > 0 {
right--
} else {
result = append(result, []int{a[i], a[left], a[right]})
for left < right && a[left] == a[left+1] {
left++
}
for left < right && a[right] == a[right-1] {
right--
}
left++
right--
}
}
}
return result
}
C#Tested in our runner
public class Solution {
public int[][] threeSum(int[] nums) {
int[] a = (int[])nums.Clone();
Array.Sort(a);
int n = a.Length;
var res = new List<int[]>();
for (int i = 0; i < n - 2; i++) {
if (a[i] > 0) break;
if (i > 0 && a[i] == a[i - 1]) continue;
int left = i + 1;
int right = n - 1;
while (left < right) {
int total = a[i] + a[left] + a[right];
if (total < 0) {
left++;
} else if (total > 0) {
right--;
} else {
res.Add(new int[] { a[i], a[left], a[right] });
while (left < right && a[left] == a[left + 1]) left++;
while (left < right && a[right] == a[right - 1]) right--;
left++;
right--;
}
}
}
return res.ToArray();
}
}
Common mistakes
- Skipping duplicates with
if nums[i] == nums[i+1]: continuefor the outer loop. This looks ahead and drops the first copy, so[-1,-1,2]is lost. Compare with the previous element,nums[i] == nums[i-1], and only wheni > 0. - Not moving past duplicates after a match, so the same triplet is added again. After recording a triplet, advance
leftwhilenums[left] == nums[left+1]and retreatrightwhilenums[right] == nums[right-1], then do one moreleft++andright--. - Forgetting the bounds in the skip loops:
while nums[left] == nums[left+1]withoutleft < right. On input like[0,0,0]this can step past the end of the array. Always writewhile left < right and .... - Returning right after the first match for a given
i. Several pairs can complete the samei, as in-3with(0,3)and(1,2). After a hit, keep both pointers moving and continue the loop. - Skipping
iusingnums[i] == nums[i-1]without sorting first. Equal values are only adjacent in sorted order, so duplicates slip through. Sort the array before the loop. - Breaking out of the outer loop when
nums[i] >= 0instead ofnums[i] > 0. That drops the[0,0,0]triplet. Break only whennums[i]is strictly positive. - Skipping duplicates with
if j > 0 and nums[j] == nums[j-1]in the hash approach. That can comparenums[j]tonums[i]and drop a valid pair like[-1,-1,2]. Usej > i + 1so the check only compares two second-position candidates.
Edge cases
[0,0,0]returns[[0,0,0]]. The break condition must allownums[i] == 0.[0,0,0,0]also returns[[0,0,0]], one triplet, not four. Duplicate skipping must handle long runs.[1,2,3]has no zero-sum triplet and returns[]. The early break on a positive first value covers this.[-1,-1,2]returns[[-1,-1,2]]. The two-1values are different indices, so reusing a value is allowed when it appears twice.[-2,0,0,2,2]returns[[-2,0,2]]once, even though two zeros and two twos could form four index combinations.- All negative values, such as
[-5,-4,-3], return[]. Pointers close without a hit. - Maximum size with 3000 values: the O(n^2) approaches finish in well under a second, while brute force does not.
Follow-ups interviewers ask
- Can you solve it without sorting?
- Yes, with a hash set per fixed element. You then need another way to remove duplicates, such as storing sorted triplets in a set. That keeps O(n^2) time but needs extra memory for the set and more hashing, so sorting is usually the cleaner choice.
- How would you generalize this to 4Sum or kSum?
- Sort the array, then recurse. Fix one number and solve (k-1)Sum on the rest, until you reach Two Sum with two pointers. The time is O(n^(k-1)) for k >= 2, ignoring the sort. Duplicate skipping works the same way at every level.
- What if you only need to count the triplets, or find the sum closest to zero?
- The same sort and two pointers work. For closest, track the best absolute difference as the pointers move, and move the pointers by the sign of the current sum. Counting with duplicates needs care: when the pair values match, count combinations from run lengths instead of skipping.
3Sum FAQ
What is the time complexity of 3Sum?
The two pointers solution runs in O(n^2) time, where n is the array length. Sorting costs O(n log n), and each of the n fixed values triggers one O(n) pointer sweep. The brute force triple loop is O(n^3).
Why use two pointers for 3Sum?
After sorting, the sum of the two pointed values moves predictably. A small sum means only the left pointer can fix it, and a large sum means only the right pointer can. So each step safely discards one value, and one sweep finds every pair for the fixed number.
Can 3Sum be solved in O(1) extra space?
Almost. The two pointers version uses only a few integers beyond the sort and the output. An in-place sort such as heap sort gives true O(1) extra space, while most built-in sorts use O(log n) or O(n) space. The output list is not counted.
Why does 3Sum sort the array first?
Sorting enables both the pointer movement rule and the cheap duplicate check. Equal values land next to each other, so you compare with a neighbour instead of keeping a set of triplets. The O(n log n) sort is dominated by the O(n^2) sweep.
How do you avoid duplicate triplets in LeetCode 15?
Skip a fixed value if it equals the previous fixed value. After finding a triplet, move left forward past equal values and right backward past equal values. Every triplet then has a distinct first, second and third value combination.
Is a hash map solution for 3Sum as fast as two pointers?
Both are O(n^2) time. The hash map version uses O(n) extra space and pays hashing costs on each pair, so two pointers is usually faster in practice and uses less memory.
Asked at
See which companies ask this — Pro
Related problems
- Container With Most Water · same technique: Converging (Sorted Array Target Sum)
- Two Sum II - Input Array Is Sorted · same technique: Converging (Sorted Array Target Sum)
- 4Sum · same technique: Converging (Sorted Array Target Sum)
- Boats to Save People · same technique: Converging (Sorted Array Target Sum)
- 3Sum Closest · same technique: Converging (Sorted Array Target Sum)
- Trapping Rain Water · next harder, same pattern
- Sort Colors · same pattern: Two Pointers
- Longest Palindromic Substring · same pattern: Two Pointers
- Remove Nth Node From End of List · same pattern: Two Pointers
- Find the Duplicate Number · same pattern: Two Pointers