Definition
- 3Sum variant – find all unique triplets summing to zero using sort plus two-pointer pair search.
- Fix one, scan two – the outer loop picks the first triplet member; the inner two-pointer scan finds the completing pair.
- Duplicate skipping – three skip points prevent the same triplet from appearing more than once.
- Time – O(n squared) total; the O(n log n) sort is absorbed by the quadratic scan.
- Space – O(1) extra beyond the sort and the output.
The National Bank of India wants to find every set of three ledger adjustments that net to zero so they cancel out. Rajesh sorts the adjustments, fixes the first one, and uses two fingers from the ends of the rest to find a matching pair that brings the total to zero, skipping repeats so he never reports the same trio twice.
Understanding the Concepts
What is this variant of 3Sum?
This is the same 3Sum problem, find all unique triplets summing to zero, approached with the sort-then-two-pointer strategy. The emphasis here is on the pair-search inner loop: after fixing one element, the remaining problem is a sorted two-sum, which the opposite-end two-pointer solves in O(n) per fixed element.
package com.bank.dsa;
import java.util.*;
public class LedgerNettingService {
public List<List<Integer>> findCancellingTrios(int[] adjustments) {
Arrays.sort(adjustments);
List<List<Integer>> result = new ArrayList<>();
// implementation below
return result;
}
}
How does the outer loop work?
The outer loop iterates i from 0 to n - 3, fixing adjustments[i] as the first member of the triplet. If the fixed element equals the previous one, skip it to avoid duplicate triplets. If the fixed element is greater than zero (target is zero), break early because all remaining sums will be positive.
for (int i = 0; i < n - 2; i++) {
if (i > 0 && adjustments[i] == adjustments[i - 1]) continue;
if (adjustments[i] > 0) break;
// inner two-pointer scan
}
How does the inner two-pointer scan work?
For each fixed i, set left = i + 1 and right = n - 1. Compute sum = adjustments[i] + adjustments[left] + adjustments[right]. If the sum equals zero, record the triplet and skip duplicates on both pointers. If the sum is negative, move left up. If positive, move right down.
package com.bank.dsa;
import java.util.*;
public class ThreeSumPairSearch {
public static List<List<Integer>> threeSum(int[] a) {
Arrays.sort(a);
List<List<Integer>> result = new ArrayList<>();
int n = a.length;
for (int i = 0; i < n - 2; i++) {
if (i > 0 && a[i] == a[i - 1]) continue;
if (a[i] > 0) break;
int left = i + 1, right = n - 1;
while (left < right) {
int sum = a[i] + a[left] + a[right];
if (sum == 0) {
result.add(List.of(a[i], a[left], a[right]));
while (left < right && a[left] == a[left + 1]) left++;
while (left < right && a[right] == a[right - 1]) right--;
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] adjustments = {-4000, -2000, -1000, 0, 1000, 2000, 3000, 4000};
List<List<Integer>> trios = threeSum(adjustments);
for (List<Integer> trio : trios) {
System.out.println(trio);
}
}
}
[-4000, 1000, 3000]
[-4000, 0, 4000]
[-3000, -1000, 4000]
[-3000, 0, 3000]
[-3000, 1000, 2000]
[-2000, -1000, 3000]
[-2000, 0, 2000]
[-1000, 0, 1000]
Why are three duplicate-skip points needed?
Without all three skips, the output contains repeated triplets. The first skip (fixed element) prevents regenerating triplets with the same first value. The second and third skips (left and right after a match) prevent recording the same completing pair within a single fixed-element scan.
// Skip 1: outer loop
if (i > 0 && a[i] == a[i - 1]) continue;
// Skip 2: left pointer after match
while (left < right && a[left] == a[left + 1]) left++;
// Skip 3: right pointer after match
while (left < right && a[right] == a[right - 1]) right--;
What is the time and space complexity?
Sorting is O(n log n). The outer loop runs n times, and each inner two-pointer scan is O(n), so the total is O(n squared) which dominates the sort. Extra space is O(1) beyond the sort and the output list. This is a big improvement over the naive O(n cubed) triple loop.
Sort: O(n log n)
Outer loop: n iterations
Inner scan: O(n) each
Total: O(n * n) = O(n squared)
Extra space: O(1)
How does this generalise to kSum?
The sort-plus-two-pointer pattern generalises to kSum by recursion. For k greater than 2, fix one element and recurse with k minus 1 on the remaining array. The base case is 2Sum solved with two pointers. The time is O(n to the power of k minus 1).
package com.bank.dsa;
import java.util.*;
public class KSumSolver {
public List<List<Integer>> kSum(int[] nums, int target, int k) {
Arrays.sort(nums);
return kSumHelper(nums, target, k, 0);
}
private List<List<Integer>> kSumHelper(int[] nums, long target, int k, int start) {
List<List<Integer>> result = new ArrayList<>();
if (k == 2) {
int left = start, right = nums.length - 1;
while (left < right) {
long sum = nums[left] + nums[right];
if (sum == target) {
result.add(new ArrayList<>(List.of(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 : kSumHelper(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 missing the outer-loop duplicate skip, which produces the same triplet from different starting positions. Another is not advancing both pointers after recording a match, which causes an infinite loop or re-records the same triplet.
// Wrong: only advance left, forget right
if (sum == 0) {
result.add(List.of(a[i], a[left], a[right]));
left++;
// BUG: right stays, may re-record
}
// Correct: advance both after skipping duplicates
if (sum == 0) {
result.add(List.of(a[i], a[left], a[right]));
while (left < right && a[left] == a[left + 1]) left++;
while (left < right && a[right] == a[right - 1]) right--;
left++;
right--;
}
What should a senior engineer know?
A senior engineer explains why sorting enables duplicate skipping, proves the three-skip sufficiency, mentions the kSum generalisation, and sorts a copy to preserve the caller's data. They also note that a hash-based 3Sum approach exists but managing duplicates with hashing is harder, making the sort-plus-two-pointer approach the cleaner standard.
Visual Overview
Sorted: [-4000, -2000, -1000, 0, 1000, 2000, 3000, 4000] Outer loop fixes element i: ┌───────────────────────────────────────────────┐ │ i=0: fix = -4000 │ │ L=1 R=7 │ │ [-4k] [-2k][-1k][ 0 ][ 1k][ 2k][ 3k][ 4k] │ │ fix L R │ │ │ │ sum = -4000 + (-2000) + 4000 = -2000 < 0 │ │ --> move L right │ │ │ │ sum = -4000 + (-1000) + 4000 = -1000 < 0 │ │ --> move L right │ │ │ │ sum = -4000 + 0 + 4000 = 0 MATCH │ │ --> record [-4000, 0, 4000] │ │ --> skip dups, advance both │ └───────────────────────────────────────────────┘ Three Duplicate Skip Points: 1. if (i > 0 && a[i] == a[i-1]) continue 2. while (a[left] == a[left+1]) left++ 3. while (a[right] == a[right-1]) right--
Key Takeaway
The 3Sum problem asks me to find every unique triplet in an array that sums to zero, and the efficient approach combines sorting with two pointers. I sort the array first, then fix each element as the first member of the triplet. For the remaining part of the array I place a left pointer just after the fixed element and a right pointer at the end, moving them inward based on whether the sum is below, above, or equal to zero.
The detail that separates a correct answer from a buggy one is duplicate handling in three distinct places. I skip a fixed element if it equals the previous fixed element, and after recording a matching triplet I advance the left pointer past repeated values and retreat the right pointer past repeated values before moving both inward. Missing any of these three skips produces the same triplet more than once.
On complexity, sorting is O(n log n), and the fixed-element loop wrapping the linear two-pointer scan is O(n squared), which dominates. Extra space is O(1) beyond the output. That is a big improvement over the naive triple loop which is O(n cubed). The same template generalises to kSum by recursion.
In my banking project at the National Bank of India, I used this in the month-end netting service. Ledger adjustments could be positive or negative, and the risk team wanted every unique group of three adjustments that cancelled to zero so they could be closed together. Because duplicate adjustment amounts were common, the three duplicate-skipping points ensured no cancelling trio was ever reported twice.
Remember one sentence: sort the array, fix one element, two-pointer the rest, and skip duplicates at three points for O(n squared) unique triplet detection.
---