18. 4Sum
Asked at Oracle, Bloomberg
Difficulty
Medium
Time
O(n^3)
Space
O(1)
Pattern
Array
Companies
2
Problem
You are given an integer array nums and an integer target. Find every group of four different positions in the array whose values add up to target, and return those groups as a list of quadruplets.
The four positions must be distinct, but the values do not have to be. For example, [2,2,2,2] is a valid answer if the array has at least four 2s. The same quadruplet must not appear twice in the answer, so [-2,0,0,2] should be listed once even if the zeros come from different positions. You may return the quadruplets in any order.
A brute-force check of all four-index combinations is too slow. The trick is to sort the array first, then fix the first two values with two loops and find the last two values with a two-pointer scan. Sorting also makes it easy to skip duplicate values at each level.
Pick four positions that sum to target
Constraints
- ●
1 <= nums.length <= 200 - ●
-10^9 <= nums[i] <= 10^9 - ●
-10^9 <= target <= 10^9
Examples
nums = [1,0,-1,0,-2,2], target = 0[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]nums = [2,2,2,2,2], target = 8[[2,2,2,2]]Asked At
2 companies| Company | Difficulty | |
|---|---|---|
| Oracle | Medium | View all Oracle questions → |
| Bloomberg | Medium | View all Bloomberg 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.
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.
Fix two values, then use two pointers
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
O(n^3) timedef 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 runs in O(n^3) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask 4Sum?
4Sum is asked at Oracle, Bloomberg. 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.