3Sum
Problem statement
You are given an integer array nums. Find every group of three different positions i, j and k whose values add up to 0, and return each group of values as a triplet [nums[i], nums[j], nums[k]].
The same triplet of values should not appear twice in the answer, even if it can be built from different positions in the array — think of de-duplicating three metrics (say, a CPU delta, a memory delta and a network delta) that happen to cancel out to zero, where you only want to report each distinct combination once, not once per matching host.
Examples
Example 1
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Explanation: -1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. Other sets of positions also add to zero, but they reuse the same three values as one of these two triplets, so they aren't counted again.
Example 2
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Explanation: The only possible triplet uses all three zeros, and it sums to zero.
Hints
Approach
Optimal: Two pointers
Intuition
Sorting turns "find two numbers matching a target" into something two fingers can do together: put one at the start of the remaining range and one at the end. If the pair sums too low, the left finger moves right (toward bigger numbers); if it sums too high, the right finger moves left (toward smaller numbers). Because the array is sorted, every move is guaranteed to get you closer, so neither finger ever needs to backtrack. That's what makes this faster in practice than the hash-set version — no extra set to build or hash, just index arithmetic.
Steps
- Sort
nums. - Loop
ifrom the start up to (but not including) the last two positions, treatingnums[i]as the fixed first number. - Skip
iif it repeats the previous value, and stop the whole loop oncenums[i] > 0. - Set
left = i + 1andright = n - 1. - While
left < right, look attotal = nums[i] + nums[left] + nums[right].- If
total < 0, moveleftright (needs a bigger number). - If
total > 0, moverightleft (needs a smaller number). - If
total == 0, record the triplet, move both pointers inward, and skip past any repeated values at the newleftandrightso the same triplet isn't recorded twice.
- If
Dry run
nums = [-4, -1, -1, 0, 1, 2] (sorted), fixing i = 1 (nums[i] = -1), so left = 2, right = 5:
| left | right | nums[left] | nums[right] | total | action |
|---|---|---|---|---|---|
| 2 | 5 | -1 | 2 | 0 | match (-1, -1, 2) → left=3, right=4 |
| 3 | 4 | 0 | 1 | 0 | match (-1, 0, 1) → left=4, right=3, loop ends |
Both example triplets are found in two steps once i is fixed on the first -1.
Edge cases: an array with fewer than 3 elements never enters the outer loop, so it returns an empty list; when every value is 0, the total == 0 branch fires once and the duplicate-skipping while loops immediately close the window, so [0, 0, 0] is reported exactly once.
Complexity
Time O(n²) - sorting costs O(n log n). Then, for each of the n choices of the fixed number, the two pointers walk toward each other, giving O(n) work per fixed number and O(n²) overall.
Space O(1) - extra, not counting the space the sort itself uses or the output — no hash set is needed once the array is sorted, only a constant number of pointers are needed.
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
nums.sort()
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]])
left += 1
right -= 1
while left < right and nums[left] == nums[left - 1]:
left += 1
while left < right and nums[right] == nums[right + 1]:
right -= 1
return result
if __name__ == "__main__":
print(Solution().threeSum([-1, 0, 1, 2, -1, -4])) # [[-1, -1, 2], [-1, 0, 1]]
print(Solution().threeSum([0, 0, 0])) # [[0, 0, 0]]RecapThe whole problem in a few lines, for the night before
- Spot it: "find triplets/groups of numbers that sum to a target" in an unsorted array
- Idea: sort first, then fix one number and use two pointers on the rest to find the other two
- Cost: O(n²) time, O(1) extra space (not counting the sort or the output)
- Trap: forgetting to skip repeated values for the fixed number *and* for both pointers — this is what causes duplicate triplets in the output
Interview follow-ups
What if the problem were 4Sum instead of 3Sum?
Add one more level of fixed-number looping before falling back to the same two-pointer scan: fix
nums[i], then fixnums[j]forj > i, then run the two-pointer walk on the remaining range to find pairs summing totarget - nums[i] - nums[j]. This generalizes to k-sum by recursing down to a 2-pointer base case once only two numbers are left, at a cost of O(n^(k-1)) time for k-sum.The array is too large to sort in memory — how would you find zero-sum triplets across a dataset that doesn't fit?
Since the two-pointer approach depends on random access into a sorted array, an external merge sort (sorting on-disk chunks, then merging) would produce a sorted stream you can still scan with two pointers reading from disk or a memory-mapped file. Alternatively, if approximate results are acceptable, values could be bucketed by range across machines so that any triplet summing to zero is guaranteed to have its three values land in a small, related set of buckets, letting each bucket group be solved independently in memory.
Frequently asked questions
Sorting is what makes the two-pointer scan possible: once the array is ordered, moving the left pointer right always increases the sum and moving the right pointer left always decreases it, so you know exactly which direction to move without checking every pair. Sorting also puts equal values next to each other, which is what lets you skip duplicates with a simple neighbor check instead of a separate lookup structure.
The underlying pattern — combine three signals from a batch of readings to see which combinations cancel out or hit a target — shows up in capacity and cost reconciliation, such as finding three resource deltas (say, CPU, memory and network headroom changes across a migration) that sum to zero. It's also a standard way interviewers check whether a candidate can turn an O(n³) brute force into an O(n²) solution using sorting and two pointers, a skill that generalizes to a lot of "scan sorted data efficiently" tasks in infra tooling.
Almost nothing — replace every 0 in the two-pointer approach with k: fix nums[i], then look for two remaining numbers whose sum is k - nums[i] using the same left/right pointer walk. The sorting, the duplicate-skipping and the O(n²) time complexity all stay the same.
Each pointer can independently land on a repeated value from a previous match. Skipping only i would still let the same pair of left/right values be recorded twice when nums[i] is fixed; skipping only left/right would still let the same fixed number nums[i] be processed twice, doing the same inner work again. All three checks together are what keeps each distinct value-triplet in the output exactly once.
