How Do You Solve the Four Sum Problem?
Learn how to solve the four sum problem in O(n cubed) time by extending the three-sum two-pointer pattern.
Expected Interview Answer
Sort the array, then use two nested loops to fix the first two elements and a two-pointer sweep on the remainder to find pairs completing the target sum, giving O(n cubed) time by extending the three-sum pattern with one more fixed layer.
After sorting, the outer two loops fix indices i and j (with j starting after i), and the inner two pointers, left just after j and right at the array’s end, sweep to find pairs where all four values sum to the target. If the four-way sum is too small, left moves forward; if too large, right moves backward; a match is recorded and both pointers skip past duplicate values. Duplicate skipping must happen at all four levels — i, j, left, and right — to avoid repeated quadruplets, and light pruning (skipping when the smallest possible or largest possible sum at a fixed i, j cannot reach the target) keeps the practical runtime reasonable. This same nested-fix-plus-two-pointer pattern generalizes directly to k-sum for any k by recursing one layer deeper per additional fixed element.
- O(n cubed) time by directly extending the three-sum pattern
- O(1) extra space beyond the initial sort
- Systematic duplicate skipping at every fixed level
- Generalizes cleanly to k-sum via recursion
AI Mentor Explanation
Sort every player’s strike-rate delta from lowest to highest, then fix two players with nested loops and sweep the remaining players with two pointers to find a pair whose deltas complete a four-player combination hitting the target total exactly. If the running four-way total is short of target, the lower pointer moves toward higher deltas; if it overshoots, the upper pointer moves toward lower deltas. A match gets logged as a valid four-player combo, and all four index levels skip past repeated delta values so the same combo is never logged twice. This nests one more nested loop on top of the three-sum trick, trading an extra factor of n for the ability to fix one more player.
Step-by-Step Explanation
Step 1
Sort the array
Sorting enables ordered two-pointer sweeping and duplicate skipping at every level.
Step 2
Fix two outer indices
Loop i, then j starting after i, skipping repeated values at each level to avoid duplicate quadruplets.
Step 3
Two-pointer sweep on the remainder
Set left = j+1, right = n-1; move left up or right down based on whether the four-way sum is below or above target.
Step 4
Record matches and prune
On a match, save the quadruplet and skip duplicates at both pointers; optionally prune i, j ranges whose min/max sums cannot reach target.
What Interviewer Expects
- Recognize this as three-sum with one additional fixed outer loop
- State the O(n cubed) time complexity and explain the extra factor of n versus three-sum
- Explain duplicate skipping at all four index levels (i, j, left, right)
- Mention pruning as an optional optimization, not a correctness requirement
Common Mistakes
- Forgetting to skip duplicates at the outer j loop, not just the innermost pointers
- Using nested hash lookups without sorting, losing the clean two-pointer structure
- Not handling integer overflow risk when summing four large values (language-dependent)
- Assuming four sum is meaningfully different in approach from three sum rather than a direct extension
Best Answer (HR Friendly)
“Four sum is the same idea as three sum but with one more number fixed. I sort the array, use two nested loops to fix the first two numbers, and then run the same two-pointer sweep on the rest to find a pair that completes the target. It costs one more factor of n in time because I am fixing one more position.”
Code Example
def four_sum(nums, target):
nums.sort()
n = len(nums)
result = []
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left, right = j + 1, n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total < target:
left += 1
elif total > target:
right -= 1
else:
result.append([nums[i], nums[j], 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 generalize this to solve k-sum for an arbitrary k?
- What pruning could you add to skip fixed pairs (i, j) that cannot possibly reach the target?
- How would integer overflow risk change your implementation in a language like Java or C++?
- How would you count all valid quadruplets instead of listing them, and would that change the complexity?
MCQ Practice
1. What is the time complexity of the standard sort-and-two-pointer four sum solution?
Two nested outer loops fix the first two elements, and the inner two-pointer sweep is O(n), giving O(n cubed) overall.
2. How does the four sum algorithm relate to the three sum algorithm?
Four sum directly extends three sum by fixing one additional index before running the same two-pointer sweep on the remainder.
3. At how many index levels must duplicate values be skipped to avoid duplicate quadruplets?
Duplicates must be skipped at both outer fixed indices (i and j) and at both moving pointers (left and right).
Flash Cards
What is the time complexity of the sorted two-pointer four sum solution? — O(n cubed).
How does four sum extend the three-sum pattern? — It adds one more nested fixed loop before running the same two-pointer sweep.
How many index levels need duplicate skipping in four sum? — All four: both fixed indices and both pointers.
What general technique does four sum illustrate? — The k-sum pattern, extendable by recursing one more fixed layer per additional element.