4Sum
Asked at Oracle
Problem
Given an array nums of n integers and an integer target, find all unique quadruplets that sum to target. This problem extends 3Sum by adding a fourth pointer, testing your ability to handle nested loops and duplicate skipping.
Asked At
| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
How to Think About It
Brute force: four nested loops checking every quadruplet. That's O(n^4) - far too slow. The two-pointer optimization reduces the innermost two loops to O(n).
Key insight: sort the array, fix two elements (i, j), then use two pointers (left, right) for the remaining pair. This brings it to O(n^3). Skip duplicates at all four levels.
Why sorting helps: it makes duplicate skipping easy. After fixing i and j, the two-pointer scan on the inner pair works the same as in 3Sum. If current sum < target, move left right; if > target, move right left.
Duplicate skipping rules: skip duplicate nums[i] values (i > 0 and nums[i] == nums[i-1]). Skip duplicate nums[j] values (j > i and nums[j] == nums[j-1]). Skip duplicate left values after finding a valid quadruplet. Skip duplicate right values similarly.
Visual walkthrough for nums = [1, 0, -1, 0, -2, 2] target = 0:
Sort: [-2, -1, 0, 0, 1, 2]
i=0, nums[i]=-2. j=1, nums[j]=-1. left=2, right=5.
-2 + -1 + 0 + 2 = -1 < 0. Move left.
-2 + -1 + 0 + 2 = -1 < 0. Move left.
-2 + -1 + 1 + 2 = 0. Found [-2,-1,1,2]. Skip dups. left=4, right=4. Stop.
j=2, nums[j]=0. left=3, right=5.
-2 + 0 + 0 + 2 = 0. Found [-2,0,0,2]. left=4, right=4. Stop.
j=3, nums[j]=0. Same as j=2. Skip.
i=1, nums[i]=-1. j=2, nums[j]=0. left=3, right=5.
-1 + 0 + 0 + 2 = 1 > 0. Move right. left meets right.
j=3, same as j=2. Skip.
Result: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]
Edge cases: fewer than 4 elements (return empty), all elements same and equal to target/4, no valid quadruplets.
Optimal Approach
Step 1: Sort the array.
Step 2: For each i from 0 to n-4 (skip duplicates):
For each j from i+1 to n-3 (skip duplicates):
- Set left = j+1, right = n-1
- Compute sum = nums[i] + nums[j] + nums[left] + nums[right]
- If sum == target: add to result, skip duplicates on both sides
- If sum < target: move left right
- If sum > target: move right left
Walkthrough with nums = [1, 0, -1, 0, -2, 2] target = 0:
- Sort: [-2, -1, 0, 0, 1, 2]
- i=0, j=1: -2 + (-1) + 0 + 2 = -1. Move left.
- i=0, j=1: -2 + (-1) + 1 + 2 = 0. Found [-2,-1,1,2].
- i=0, j=2: -2 + 0 + 0 + 2 = 0. Found [-2,0,0,2].
- i=1, j=2: -1 + 0 + 0 + 2 = 1. Move right.
- All done.
Time: O(n^3) - two outer loops O(n^2), inner two-pointer O(n). Space: O(1) excluding output.
What Trips People Up in Real Interviews
Forgetting to skip duplicates at the j level. After skipping duplicates at i, you must also skip duplicate j values inside the i loop. Otherwise you get duplicate quadruplets.
Using O(n^4) brute force without recognizing the two-pointer optimization. Fix two elements and two-pointer the rest - this is the standard kSum pattern.
Integer overflow when summing four values. In languages like Java/C++, use long for the sum if values can be large. Python handles big integers natively.
Off-by-one errors in loop bounds. The outer loop goes to n-4, the j loop to n-3, and left starts at j+1. Getting these wrong causes index out of bounds or missed quadruplets.
Not returning early when the smallest possible sum exceeds target. After sorting, if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target, no further quadruplets exist - break early.
Solution Code
def fourSum(nums, target):
nums.sort()
result = []
n = len(nums)
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
lo, hi = j + 1, n - 1
while lo < hi:
total = nums[i] + nums[j] + nums[lo] + nums[hi]
if total < target:
lo += 1
elif total > target:
hi -= 1
else:
result.append([nums[i], nums[j], nums[lo], nums[hi]])
while lo < hi and nums[lo] == nums[lo + 1]:
lo += 1
while lo < hi and nums[hi] == nums[hi - 1]:
hi -= 1
lo += 1
hi -= 1
return resultFrequently Asked Questions
What is the 4Sum problem?
Given an array nums of n integers and an integer target, find all unique quadruplets that sum to target. This problem extends 3Sum by adding a fourth pointer, testing your ability to handle nested loops and duplicate skipping.
How do you solve 4Sum?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask 4Sum?
4Sum is asked at Oracle. It is a medium difficulty problem.
What are common mistakes on 4Sum?
- Forgetting to skip duplicates at the j level. After skipping duplicates at i, you must also skip duplicate j values inside the i loop. Otherwise you get duplicate quadruplets.
- Using `O(n^4)` brute force without recognizing the two-pointer optimization. Fix two elements and two-pointer the rest - this is the standard kSum pattern.
- Integer overflow when summing four values. In languages like Java/C++, use long for the sum if values can be large. Python handles big integers natively.
- Off-by-one errors in loop bounds. The outer loop goes to n-4, the j loop to n-3, and left starts at j+1. Getting these wrong causes index out of bounds or missed quadruplets.
- Not returning early when the smallest possible sum exceeds target. After sorting, if nums[i] + nums[i+1] + nums[i+2] + nums[i+3] > target, no further quadruplets exist - break early.