Definition
- 4Sum – an extension of the 3Sum pattern where you fix one additional element with an outer loop before running the familiar two-pointer scan.
- Sorting – the array is sorted once so that duplicate values sit next to each other and the two-pointer convergence works.
- Duplicate skipping – at each of the four selection levels (outer index, inner index, left pointer, right pointer) you skip values equal to their predecessor to guarantee unique quadruplets.
- Two-pointer scan – after fixing two elements, the remaining two are found by moving a left pointer rightward and a right pointer leftward toward the target remainder.
- Generalization – the same skeleton extends to k-sum by recursively fixing elements and reducing the dimension by one until you reach the two-pointer base case.
At the National Bank of India, Rajesh investigates structured transactions where exactly four payment amounts combine to hit an exact target figure. He lines up all the amounts in order, picks the first two amounts from the left, and then uses the two-pointer squeeze on the rest to find pairs that complete the target. He skips repeated amounts at every stage so no group of four is reported twice.
Understanding the Concepts
What is the 4Sum problem?
The 4Sum problem asks you to find every unique group of four numbers (a quadruplet) in an array whose sum equals a given target. The result must contain no duplicate quadruplets, and each quadruplet must list its elements in non-decreasing order. This is a direct extension of the well-known 3Sum problem with one extra level of nesting.
In a banking context, the National Bank of India compliance team investigates cases where four transaction amounts together equal a suspicious target figure, indicating a single large payment split across four legs.
package com.bank.coding;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class FourSumFinder {
public static List<List<Integer>> fourSum(int[] amounts, int target) {
List<List<Integer>> result = new ArrayList<>();
if (amounts == null || amounts.length < 4) return result;
Arrays.sort(amounts);
int n = amounts.length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && amounts[i] == amounts[i - 1]) continue; // skip duplicate first
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && amounts[j] == amounts[j - 1]) continue; // skip duplicate second
int left = j + 1, right = n - 1;
while (left < right) {
long sum = (long) amounts[i] + amounts[j] + amounts[left] + amounts[right];
if (sum == target) {
result.add(Arrays.asList(amounts[i], amounts[j], amounts[left], amounts[right]));
while (left < right && amounts[left] == amounts[left + 1]) left++; // skip dup left
while (left < right && amounts[right] == amounts[right - 1]) right--; // skip dup right
left++;
right--;
} else if (sum < target) {
left++;
} else {
right--;
}
}
}
}
return result;
}
}
Why does 4Sum build on 3Sum?
The 3Sum pattern fixes one element, then uses a two-pointer scan for the remaining two. The 4Sum pattern adds one more fixed loop on top. By fixing two elements with nested loops, the remaining problem reduces to a two-sum search that the two-pointer technique handles in linear time. This layering is what gives the O(n^3) time complexity: two loops each cost O(n) and the inner two-pointer scan costs O(n).
// Conceptual reduction:
// 4Sum(target) -> for each a: 3Sum(target - a)
// 3Sum(remainder) -> for each b: 2Sum(remainder - b)
// 2Sum is solved with two pointers on a sorted array
How does the two-pointer scan work after fixing two elements?
After fixing the first element at index i and the second at index j, you set left = j + 1 and right = n - 1. You compute the sum of all four values. If the sum equals the target, you record the quadruplet and move both pointers inward. If the sum is less than the target, you move the left pointer right to increase the sum. If the sum is greater, you move the right pointer left to decrease it.
package com.bank.coding;
public class TwoPointerDemo {
public static void demonstrate() {
int[] sorted = {-2, -1, 0, 0, 1, 2};
int target = 0;
// Fix i=0 (-2), j=1 (-1), need left+right = 3
// left=2 (0), right=5 (2): sum = -2 + -1 + 0 + 2 = -1 < 0, move left
// left=3 (0), right=5 (2): sum = -2 + -1 + 0 + 2 = -1 < 0, move left
// left=4 (1), right=5 (2): sum = -2 + -1 + 1 + 2 = 0 == target, record!
System.out.println("Found: [-2, -1, 1, 2]");
}
}
How do you handle duplicate quadruplets?
Duplicate skipping happens at all four selection levels. At the outer loop, if amounts[i] equals amounts[i - 1], skip it. At the inner loop, if amounts[j] equals amounts[j - 1] within the current i iteration, skip it. After recording a quadruplet, advance left past all repeated values and retreat right past all repeated values. These four skips guarantee that every reported quadruplet is unique without storing results in a set.
package com.bank.coding;
public class DuplicateSkipDemo {
public static void showSkipping() {
int[] amounts = {-2, -1, -1, 0, 0, 1, 2, 2};
int target = 0;
// i=0 (-2): j=1 (-1), j=2 (-1) is skipped because amounts[2]==amounts[1]
// After finding a quad, left skips past repeated 0s, right skips past repeated 2s
// This prevents [-2, -1, 0, 2] from appearing twice
System.out.println("Duplicates handled at all four levels");
}
}
What about integer overflow?
When summing four values that are close to Integer.MAX_VALUE or Integer.MIN_VALUE, the sum can overflow a 32-bit int. You must cast to long before adding. In a banking context where amounts can be large, this is a real concern.
package com.bank.coding;
public class OverflowDemo {
public static void showOverflow() {
int[] amounts = {1000000000, 1000000000, 1000000000, 1000000000};
int target = -294967296; // would overflow with int sum
// Wrong: int sum overflows
int wrongSum = amounts[0] + amounts[1] + amounts[2] + amounts[3]; // overflows!
System.out.println("Wrong sum (overflow): " + wrongSum);
// Correct: cast to long
long correctSum = (long) amounts[0] + amounts[1] + amounts[2] + amounts[3];
System.out.println("Correct sum (long): " + correctSum);
}
}
Wrong sum (overflow): -294967296
Correct sum (long): 4000000000
How does this generalize to k-sum?
The same template works for any k-sum. You recursively fix elements until the dimension reduces to 2, then apply the two-pointer base case. Each recursive fix adds one factor of n to the time complexity, giving O(n^(k-1)) total.
package com.bank.coding;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class KSumSolver {
public static List<List<Integer>> kSum(int[] nums, long target, int k, int start) {
List<List<Integer>> result = new ArrayList<>();
if (start >= nums.length) return result;
if (k == 2) {
int left = start, right = nums.length - 1;
while (left < right) {
long sum = (long) nums[left] + nums[right];
if (sum == target) {
result.add(new ArrayList<>(Arrays.asList(nums[left], nums[right])));
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++; right--;
} else if (sum < target) left++;
else right--;
}
} else {
for (int i = start; i < nums.length - k + 1; i++) {
if (i > start && nums[i] == nums[i - 1]) continue;
for (List<Integer> sub : kSum(nums, target - nums[i], k - 1, i + 1)) {
sub.add(0, nums[i]);
result.add(sub);
}
}
}
return result;
}
}
What are common mistakes?
The most common mistake is forgetting to skip duplicates at one of the four levels, which causes duplicate quadruplets in the output. Another mistake is not using long for the sum, which causes integer overflow for large inputs.
package com.bank.coding;
import java.util.Arrays;
public class CommonMistakes {
// WRONG: missing duplicate skip at inner loop
public static void wrongVersion(int[] nums, int target) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < nums.length - 2; j++) {
// BUG: no duplicate skip for j!
// This produces duplicate quadruplets
// Fix: add "if (j > i + 1 && nums[j] == nums[j-1]) continue;"
}
}
}
// WRONG: using int for sum
public static void wrongOverflow(int[] nums) {
// BUG: int sum can overflow with 4 large values
int sum = nums[0] + nums[1] + nums[2] + nums[3];
// Fix: long sum = (long) nums[0] + nums[1] + nums[2] + nums[3];
}
}
What is the time and space complexity?
The time complexity is O(n^3). Sorting takes O(n log n). The two nested loops contribute O(n^2) and the two-pointer scan inside contributes O(n), giving O(n^3) total. The space complexity is O(1) extra beyond the result list, since sorting is in-place and no additional data structures are needed.
| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute force (4 nested loops) | O(n^4) | O(1) | Too slow for large inputs |
| Sort + two fix loops + two pointers | O(n^3) | O(1) | Optimal for 4Sum |
| Hash map for inner pair | O(n^3) worst case | O(n^2) | Harder duplicate handling |
| Generalized k-sum recursive | O(n^(k-1)) | O(k) recursion | Flexible for any k |
What about early termination optimizations?
You can prune the search by checking if the smallest possible sum (using the four smallest remaining elements) exceeds the target, or if the largest possible sum (using the four largest) is less than the target. These checks let you skip entire iterations of the outer loops when no valid quadruplet can exist in that range.
package com.bank.coding;
public class EarlyTermination {
public static void optimizedOuterLoop(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n - 3; i++) {
// Prune: smallest possible sum with current i
long minSum = (long) nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3];
if (minSum > target) break; // all future i values will be even larger
// Prune: largest possible sum with current i
long maxSum = (long) nums[i] + nums[n - 3] + nums[n - 2] + nums[n - 1];
if (maxSum < target) continue; // this i is too small, try next
// ... proceed with inner loop and two pointers
}
}
}
What are common interview follow-up questions?
Interviewers often ask how you would handle the problem if duplicates were allowed in the output, how you would extend to 5Sum or general k-sum, and whether a hash-based approach would be better. They may also ask about the tradeoff between the sorting-based approach and a set-based deduplication approach. The sorting approach is preferred because it handles duplicates naturally and uses less space.
// Follow-up: if duplicates are allowed, simply remove the skip logic
// Follow-up: for k-sum, use the recursive kSum method shown above
// Follow-up: hash approach stores pairs in a map, but duplicate handling is complex
Visual Overview
4Sum Algorithm Flow
==================
Sorted array: [-2, -1, 0, 0, 1, 2] Target: 0
Fix i=0 (-2)
├── Fix j=1 (-1) Need left+right = 3
│ ├── left=2(0), right=5(2): sum=-1 < 0 → move left
│ ├── left=3(0), right=5(2): sum=-1 < 0 → move left
│ └── left=4(1), right=5(2): sum=0 == 0 → RECORD [-2,-1,1,2]
│
├── Fix j=2 (0) Need left+right = 2
│ ├── left=3(0), right=5(2): sum=0 == 0 → RECORD [-2,0,0,2]
│ └── left=4(1), right=4: left >= right → stop
│
└── Fix j=3 (0) j=3 same as j=2 → SKIP duplicate
Fix i=1 (-1)
├── Fix j=2 (0) Need left+right = 1
│ └── left=3(0), right=5(2): sum=1 > 0 → move right
│ left=3(0), right=4(1): sum=0 == 0 → RECORD [-1,0,0,1]
└── ...
Result: [[-2,-1,1,2], [-2,0,0,2], [-1,0,0,1]]
Duplicate Skip Points
=====================
Level 1: i loop → skip if amounts[i] == amounts[i-1]
Level 2: j loop → skip if amounts[j] == amounts[j-1] (within i)
Level 3: left ptr → skip past repeated values after recording
Level 4: right ptr → skip past repeated values after recording
k-Sum Generalization
====================
┌──────────┐
│ k-Sum │ Fix one element, recurse on (k-1)-Sum
└────┬─────┘
│
┌────▼─────┐
│ (k-1)Sum │ Fix one element, recurse on (k-2)-Sum
└────┬─────┘
│
... (repeat until k=2)
│
┌────▼─────┐
│ 2-Sum │ Two-pointer scan on sorted remainder
└──────────┘
Key Takeaway
The 4Sum problem asks you to find every unique group of four numbers that adds up to a target, and the cleanest way to see it is as 3Sum with one extra fixed level on top. You sort the array once, use two nested loops to fix the first and second elements, and for each fixed pair you run the familiar two-pointer scan over the rest to find the remaining two elements that complete the target. The sorting is what makes both the two-pointer convergence and the duplicate skipping possible.
Duplicate handling happens at all four selection levels. At the outermost loop you skip a first element equal to the previous one, at the inner loop you skip a second element equal to the previous one within that iteration, and after recording a quadruplet you advance the left pointer past repeated values and retreat the right pointer past repeated values. Those four skips guarantee that every quadruplet you report is unique without storing results in a set for deduplication.
At the National Bank of India, Rajesh used this pattern in the compliance team to detect structured transactions where exactly four payment amounts combined to hit an exact target figure. The team needed every unique quadruple so each case could be reviewed, and the sorted two-pointer approach found them in O(n^3) time instead of the O(n^4) brute force that would have been impractical at production volumes.
The senior-level insight is that this skeleton generalizes to any k-sum problem. You recursively fix elements and reduce the dimension by one until you reach the two-pointer base case, giving O(n^(k-1)) time. Always use long for the running sum to avoid integer overflow, and apply early termination pruning to skip iterations where no valid quadruplet can exist.
Remember one sentence: 4Sum is 3Sum with one extra fix loop on top, two-pointer scan for the last two, and duplicate skipping at all four levels.
---