4Sum
- mosesg1123
- May 27
- 5 min read
This is a great follow-up to 2Sum and 3Sum. It challenges you to apply the same two-pointer strategy but adds complexity by requiring a quadruplet instead of a pair or triplet. This kind of problem comes up when you're working on systems that require combinatorial sum checks, like budgeting scenarios, fraud detection with transaction records, or even algorithmic trading strategies. The key here is optimization over brute-force enumeration.
Problem Statement
Given an array nums of n integers and an integer target, return all unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
nums[a] + nums[b] + nums[c] + nums[d] == targetYou must not return duplicate quadruplets.
Example:
Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
1. Clarify Requirements Before Jumping Into Code
We’re given an integer array and a target sum. We need to return all unique quadruplets that add up to that target.
Key clarifications:
Each number in a quadruplet must come from a unique index.
We must avoid duplicates in the result.
The result can be returned in any order, but each quadruplet must be sorted internally or de-duplicated somehow.
2. Identify the Category of the Question
This is a k-sum problem, with k = 4.
It belongs to the sorting + two pointers family and is an extension of:
2Sum (hash map or two pointers)
3Sum (fix one, use two pointers)
Common patterns:
Sorting the input
Fixing variables in a nested loop
Two-pointer scanning to find sums
Skipping duplicates
3. Consider a Brute‑Force Approach to Understand the Problem
A brute-force solution would check all possible combinations of 4 elements in the array and see if their sum equals the target.
That would be:
4 nested loops
Total time complexity: O(n⁴)
Completely impractical for larger arrays.
Still, it gives us a foundation to start from: how do we reduce the number of nested loops?
4. Brainstorm More Solutions
This is sounding very similar to the 3Sum problem, so like we did with the 3Sum Closest problem, let's start by reminding ourselves of the solution:
Step 1: Sort the array.
Step 2: Loop through each element i as the first number of the triplet.
Step 3: For each element i, use two pointers:
left = i + 1
right = n - 1
While left < right, compute the current sum of the three numbers.
If it’s equal to the target, store it.
If the sum is less than the target, move the left pointer to increase the sum.
If the sum is greater than the target, move the right pointer to decrease the sum.
Is there a way we can build on top of that solution for the 4Sum problem? We can break down the algorithm into 2 distinct parts: the outer loop that fixes one index i, and the inner loop that applies the two-pointer scanning to the remaining subarray.
We probably can't make any changes to the inner loop - after all, it was that insight that allowed us to decreased our runtime from O(n³) to O(n²).
So, what about the outer loop? What if instead of fixing just one index, we fixed two? With two nested loops for the outer indexes and our inner loop, we'd have a runtime of O(n³) - definitely better than the O(n⁴) solution we were considering in our brute-force solution. And with so many variables we need to account for, O(n³) is probably the best we can do here.
The logic ends up looking like this:
Sort nums
Loop i from 0 to n-4
Skip duplicates for i (since they will lead to duplicate solutions)
Loop j from i+1 to n-3
Skip duplicates for j
Initialize left = j+1 and right = n-1
While left < right, compute the sum
If sum == target → store it, move both pointers, skip duplicates
If sum < target → move left
If sum > target → move right
That gives us an O(n³) solution
Key insight: By building on previous solutions for simpler versions of the same problem, fixing two indices (i, j), and applying two-pointer scanning to the remaining subarray, we reduce complexity by a whole order of magnitude.
5. Discuss Trade‑Offs Between Your Solutions
Approach | Time Complexity | Space Complexity | Pros | Cons |
Brute Force | O(n⁴) | O(1) | Simple, easy to understand | Too slow for large inputs |
Two Pointer + Sort | O(n³) | O(1) | Efficient, avoids duplicates | Still nested loops, needs careful pointer control |
6. Write Pseudocode to Structure Your Thoughts
sort(nums)
result = []
for i from 0 to n-4:
if i > 0 and nums[i] == nums[i-1]: continue
for j from i+1 to n-3:
if j > i+1 and nums[j] == nums[j-1]: continue
left = j+1
right = n-1
while left < right:
sum = nums[i] + nums[j] + nums[left] + nums[right]
if sum == target:
add quadruplet to result
left++, right--
skip duplicates at left and right
else if sum < target:
left++
else:
right--
return result
7. Consider Edge Cases
Input length < 4 → return empty list
All numbers are the same
Multiple sets of 4 numbers add to the same sum
Large positive/negative values
We handle all of them naturally with sorting and duplicate checks.
8. Write Full Code Syntax
public class FourSum {
public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
left++;
right--;
while (left < right && nums[left] == nums[left - 1]) left++;
while (left < right && nums[right] == nums[right + 1]) right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}
9. Test Your Code
public static void main(String[] args) {
FourSum solver = new FourSum();
System.out.println(solver.fourSum(new int[]{1, 0, -1, 0, -2, 2}, 0));
// Expected: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
System.out.println(solver.fourSum(new int[]{2, 2, 2, 2, 2}, 8));
// Expected: [[2, 2, 2, 2]]
System.out.println(solver.fourSum(new int[]{-3, -1, 0, 2, 4, 5}, 2));
// Expected: [[-3, -1, 2, 4]]
System.out.println(solver.fourSum(new int[]{1000000000, 1000000000, 1000000000, 1000000000}, -294967296));
// Expected: []
System.out.println(solver.fourSum(new int[]{0, 0, 0, 0}, 0));
// Expected: [[0, 0, 0, 0]]
}
10. Key Lessons to Remember for Future Questions
KSum problems scale from 2Sum by adding loops and fixing variables.
Sorting + two pointers is a common strategy to avoid brute-force.
Always use long or check for overflow when dealing with large integers.
Deduplicate results early by skipping repeated elements after sorting.
This problem strengthens your ability to generalize patterns—solving 4Sum prepares you for writing reusable KSum templates. Stay tuned for that in a follow-up post!
Good Luck and Happy Coding!
Comments