How Do You Solve the Three Sum Problem?
Learn the sort-and-two-pointer approach to solving the three sum problem in O(n squared) time for coding interviews.
Expected Interview Answer
Sort the array, fix one element at a time, then use a two-pointer sweep on the remaining subarray to find pairs that sum to the negative of the fixed element, giving O(n squared) time and O(1) extra space beyond the sort.
After sorting, iterate the fixed index i from left to right and set two pointers, left at i+1 and right at the end of the array. If the three-way sum is too small, move left forward to increase it; if too large, move right backward to decrease it; if it matches zero, record the triplet and skip past duplicate values at both pointers. Skipping the fixed index whenever it repeats the previous value avoids duplicate triplets without needing a set for deduplication. This pattern generalizes the classic two-sum-on-sorted-array trick by wrapping it in one more loop, and it is the standard building block for four sum and k-sum variants.
- O(n squared) time versus O(n cubed) brute force
- O(1) extra space after an in-place sort
- Natural duplicate-triplet skipping via sorted order
- Extends directly to four sum and general k-sum
AI Mentor Explanation
Sort every player’s net run rate from lowest to highest, then fix one player’s number and use two pointers — one starting just after the fixed player, one at the highest scorer — to find two other players whose combined rate cancels it out to zero. If the trio’s total run rate is negative, the low pointer moves right toward higher rates; if positive, the high pointer moves left toward lower rates. When you land exactly on zero, record the trio and slide both pointers inward past any repeated rate values so the same trio is not counted twice. This sweep replaces checking every possible trio of players one by one with a single, ordered pass across the sorted list.
Step-by-Step Explanation
Step 1
Sort the array
Sorting first, in O(n log n), enables the two-pointer sweep and duplicate skipping.
Step 2
Fix the first element
Loop index i from 0 to n-3, skipping i if it equals the previous value to avoid duplicate triplets.
Step 3
Two-pointer sweep
Set left = i+1, right = n-1; move left up if the sum is too small, right down if too large.
Step 4
Record and deduplicate on match
On sum == 0, save the triplet, then advance both pointers past any equal adjacent values.
What Interviewer Expects
- Justify why sorting first enables the two-pointer technique
- State O(n squared) time and explain where the extra factor of n comes from versus two-sum
- Explain duplicate skipping at both the fixed index and the two pointers
- Recognize this as the base pattern for four sum / k-sum
Common Mistakes
- Forgetting to skip duplicate values, producing repeated triplets
- Using a nested hash-set approach without sorting, missing the O(1) space benefit
- Not moving both pointers after a match, causing an infinite loop or missed triplets
- Confusing this with two-sum and forgetting the outer loop over the fixed element
Best Answer (HR Friendly)
“I sort the array first, then for each number I use two pointers to scan the rest of the array for a pair that cancels it out to zero. Sorting lets me move the pointers intelligently instead of checking every possible trio, which brings the time down from cubic to quadratic.”
Code Example
def three_sum(nums):
nums.sort()
n = len(nums)
result = []
for i in range(n - 2):
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]])
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 resultFollow-up Questions
- How would you extend this approach to four sum?
- How would you find the triplet closest to a given target instead of exactly zero?
- What changes if the array can contain duplicates you must still count separately?
- Could a hash set replace the two-pointer sweep, and what would the tradeoff be?
MCQ Practice
1. What is the time complexity of the standard sort-and-two-pointer three sum solution?
Sorting costs O(n log n), but the outer loop combined with the inner two-pointer sweep dominates at O(n squared).
2. Why is the array sorted before running the two-pointer sweep?
Sorted order lets the algorithm move left or right deterministically based on whether the sum is too small or too large, and adjacent duplicates become trivial to detect.
3. What happens if you forget to skip duplicate values at the two pointers after finding a match?
Without skipping past equal adjacent values, the same numeric triplet can be recorded more than once.
Flash Cards
What is the first step in solving three sum efficiently? — Sort the array so a two-pointer sweep becomes possible.
What is the time complexity of the sorted two-pointer three sum solution? — O(n squared).
How do you avoid duplicate triplets in three sum? — Skip repeated values at the fixed index and at both moving pointers.
What technique does three sum build on? — The two-pointer sum-on-sorted-array technique used in two sum on a sorted array.