Definition
- 3Sum (Triplet Sum to Zero) – find all unique sets of three elements whose sum is zero.
- Sort first – sorting the array in O(n log n) enables the two-pointer squeeze and duplicate skipping.
- Fix and sweep – for each fixed element, use a left and right pointer to find pairs summing to its negation.
- Duplicate avoidance – skip repeated fixed elements at the outer level and skip repeated pair values at the inner level.
- Complexity – O(n^2) time from the outer loop times the linear sweep; sorting is dominated by the quadratic work.
Imagine Rajesh at the National Bank of India has a list of signed adjustments on an account: credits (positive) and debits (negative). He needs to find every unique group of three adjustments that perfectly cancel out to zero rupees. He sorts the adjustments, fixes one at a time, and for each fixed one asks Priya to find two others from the remaining list that together cancel it, using the two-pointer squeeze from both ends.
Understanding the Concepts
What is the 3Sum problem?
Given an array of integers, find all unique triplets (a, b, c) such that a + b + c = 0. Each triplet must be unique, meaning no duplicate triplets in the result even if the array contains duplicate values.
package com.bank.service;
import java.util.*;
public class ThreeSum {
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // skip duplicate fixed element
if (nums[i] > 0) break; // early exit: no triplet can sum to zero
int target = -nums[i];
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
result.add(Arrays.asList(nums[i], 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--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] adjustments = {-4, -1, -1, 0, 1, 2};
System.out.println(threeSum(adjustments));
}
}
[[-1, -1, 2], [-1, 0, 1]]
Why sort the array first?
Sorting serves two purposes. First, it enables the two-pointer squeeze: because the array is ordered, moving the left pointer right increases the sum and moving the right pointer left decreases it. Second, it makes duplicate skipping trivial: identical values are adjacent, so a simple comparison with the previous element detects and skips them.
// Without sorting, you would need a HashSet to track seen triplets,
// which adds complexity and is harder to get right.
// With sorting, duplicates are adjacent:
// [-4, -1, -1, 0, 1, 2]
// ^^^ duplicate -1s are next to each other
How does duplicate skipping work?
Duplicate avoidance happens at two levels. At the outer level, if nums[i] equals nums[i-1], you skip this i because any triplet starting with that value was already found. At the inner level, after recording a triplet, you advance left past any repeated value and retreat right past any repeated value.
// Outer level:
if (i > 0 && nums[i] == nums[i - 1]) continue;
// Inner level (after finding a valid triplet):
while (left < right && nums[left] == nums[left + 1]) left++;
while (left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
How does the two-pointer sweep find pairs?
For each fixed element nums[i], you need two elements to its right that sum to -nums[i]. You set left = i + 1 and right = end. If the pair sum equals the target, you record the triplet. If the pair sum is less than the target, you move left right to increase it. If the pair sum is greater, you move right left to decrease it.
// Walkthrough: nums = [-4, -1, -1, 0, 1, 2], fixing nums[0]=-4
// target = 4, left=1, right=5
// sum = -1 + 2 = 1 < 4 -> left=2
// sum = -1 + 2 = 1 < 4 -> left=3
// sum = 0 + 2 = 2 < 4 -> left=4
// sum = 1 + 2 = 3 < 4 -> left=5
// left >= right, no triplet with -4
What is the early exit optimization?
Once nums[i] is greater than zero, no triplet starting at i can sum to zero because the array is sorted and everything after is at least as large. Breaking out saves unnecessary work.
// nums = [-2, -1, 0, 1, 2, 3, 4]
// When i reaches the index of 1 (value > 0):
// nums[i] + nums[left] + nums[right] >= 1 + 2 + 3 = 6 > 0
// No triplet can sum to zero -> break
if (nums[i] > 0) break;
How is this different from using a HashSet?
The hash-set approach avoids sorting by using a set to track seen values and a set of canonicalized triplets to avoid duplicates. It can be O(n^2) time but requires careful management of the triplet set and is harder to get right.
| Aspect | Sorted + Two Pointers | Hash-Set |
|---|---|---|
| Time | O(n^2) | O(n^2) average |
| Space | O(1) extra (excluding result) | O(n) for the set |
| Duplicate handling | Natural from sorting | Must canonicalize triplets |
| Implementation | Clean and predictable | Error-prone |
// Hash-set approach (less preferred):
// for each i:
// Set<Integer> seen = new HashSet<>();
// for each j > i:
// complement = -(nums[i] + nums[j])
// if (seen.contains(complement)) -> found triplet
// seen.add(nums[j]);
// Must also track found triplets in a Set to avoid duplicates
What are common mistakes?
The most common mistake is not skipping duplicates at both levels, resulting in duplicate triplets in the output.
// WRONG: missing outer skip
for (int i = 0; i < nums.length - 2; i++) {
// No duplicate check on nums[i]
// Input [-1, -1, 0, 1] would produce [-1, 0, 1] twice
}
// CORRECT: skip duplicates at both levels
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
// ... inner loop also skips duplicates after finding a match
}
How does this generalize to k-Sum?
The same skeleton generalizes to k-Sum by recursively fixing elements and dropping to a two-pointer base case. For 4Sum, you fix two elements and run two-pointer on the rest, giving O(n^3). For general k-Sum, the time is O(n^(k-1)).
package com.bank.service;
import java.util.*;
public class KSum {
public static List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private static List<List<Integer>> kSum(int[] nums, long target, int k, int start) {
List<List<Integer>> result = new ArrayList<>();
if (k == 2) {
int lo = start, hi = nums.length - 1;
while (lo < hi) {
long sum = nums[lo] + nums[hi];
if (sum == target) {
result.add(new ArrayList<>(Arrays.asList(nums[lo], nums[hi])));
while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
lo++; hi--;
} else if (sum < target) lo++;
else hi--;
}
} 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 should a senior engineer know?
A senior engineer should understand the early exit optimization, the k-Sum generalization, and the tradeoff between the sorted approach and the hash-set approach. The sorted approach is preferred in interviews because it handles duplicate triplets naturally without needing to canonicalize and store each found triplet.
The time complexity is O(n^2) with O(n log n) sorting dominated by the quadratic work. The space is O(1) extra beyond the output list.
What are common interview follow-up questions?
- Interviewers commonly ask:
- What is the time complexity? (O(n^2) from the outer loop times the linear sweep.)
- Can you avoid sorting? (Yes, hash-set approach, but it is harder to manage duplicates.)
- How would you do 4Sum? (Fix two elements, two-pointer the rest.)
- What about k-Sum? (Recursive reduction to the two-pointer base case.)
Visual Overview
Sorted array: [-4, -1, -1, 0, 1, 2] Fix nums[1] = -1, target = 1 ┌───────────────────────────────────┐ │ [-4, -1, -1, 0, 1, 2] │ │ ^i ^L ^R │ │ │ │ L=-1, R=2: sum=1 == target │ │ Record [-1, -1, 2] │ │ Skip dup L, skip dup R │ │ L→0, R→1 │ │ │ │ L=0, R=1: sum=1 == target │ │ Record [-1, 0, 1] │ │ L→R, done │ └───────────────────────────────────┘ Fix nums[2] = -1: same as nums[1] │ → skip (duplicate fixed element) │ Result: [[-1,-1,2], [-1,0,1]]
Key Takeaway
The 3Sum problem asks for every unique group of three numbers that adds up to zero. The efficient solution sorts the array first, then iterates through it fixing each element as the first member of the triplet. For each fixed element, a two-pointer sweep over the remaining portion finds pairs that complete the sum to zero.
Duplicate avoidance is clean because sorting places identical values adjacent. At the outer level you skip a fixed element that equals the previous one. After recording a triplet at the inner level, you advance both pointers past any repeated values. This guarantees no duplicate triplets without needing a hash set.
In the reconciliation service at the National Bank of India, an account accumulates signed adjustments through the day: credits positive, debits negative. The audit team needs every unique group of three adjustments that exactly cancel to zero, because such trios signal a reversal pattern worth reviewing. The sorted two-pointer approach produces a clean, duplicate-free list efficiently.
The senior-level insight is that the same sort-fix-squeeze skeleton extends directly to k-Sum by recursively fixing elements and dropping to a two-pointer base case. Recognizing that 3Sum is just one instance of this general pattern lets you adapt quickly in an interview.
Remember one sentence: sort, fix one element, two-pointer the rest for the complementary pair, and skip duplicates at every level.
---