3Sum: Sort + Fix One + Two-Pointer, Skip Duplicates

• 3Sum – find all unique triples in an array that sum to a target, typically zero.
• Sort first – sorting enables both the two-pointer pair search and easy duplicate skipping.
• Fix one, scan two – the outer loop fixes the first element; left and right pointers scan the remaining range.
• Duplicate skipping – three skip points: the fixed element, left after a match, right after a match.
• Complexity – O(n squared) time, O(1) extra space beyond the output.

What is the 3Sum problem?

The 3Sum problem asks you to find all unique triples [a, b, c] in an array such that a + b + c = 0 (or a given target). The key word is "unique": the output must not contain duplicate triples even if the input contains duplicate values. This is one of the most common interview problems and the foundation for 4Sum and kSum generalisations.

package com.bank.dsa;

import java.util.List;

public interface ThreeSumSolver {
    List<List<Integer>> threeSum(int[] nums);
}

Why sort the array first?

Sorting is the enabling step. Once the array is sorted, you can use the two-pointer technique, which relies on order: if a sum is too small you move the left pointer right to increase it, and if too large you move the right pointer left to decrease it. Sorting also places duplicates next to each other, making duplicate skipping a simple adjacent-element comparison. Without sorting you could not reason about which pointer to move.

import java.util.Arrays;

int[] amounts = {-5000, 3000, -1000, 2000, -3000, 5000, 1000};
Arrays.sort(amounts);
// amounts = [-5000, -3000, -1000, 1000, 2000, 3000, 5000]

How does the fix-one-plus-two-pointer approach work?

The outer loop fixes the first element of the triple at index i, from 0 to n-3. For each fixed element, set left = i + 1 and right = n - 1. Compute the sum of all three. If the sum equals zero, record the triple and advance both pointers. If the sum is less than zero, move left rightward. If greater, move right leftward. The inner scan is O(n) for each fixed element, so the total is O(n squared).

package com.bank.dsa;

import java.util.*;

public class WashTradeDetector {
    public static List<List<Integer>> findOffsettingTriples(int[] amounts) {
        Arrays.sort(amounts);
        List<List<Integer>> result = new ArrayList<>();
        int n = amounts.length;

        for (int i = 0; i < n - 2; i++) {
            // Skip duplicate fixed element
            if (i > 0 && amounts[i] == amounts[i - 1]) continue;

            // Early exit: if fixed element > 0, no triple can sum to 0
            if (amounts[i] > 0) break;

            int left = i + 1, right = n - 1;
            while (left < right) {
                int sum = amounts[i] + amounts[left] + amounts[right];
                if (sum == 0) {
                    result.add(List.of(amounts[i], amounts[left], amounts[right]));
                    // Skip duplicate left
                    while (left < right && amounts[left] == amounts[left + 1]) left++;
                    // Skip duplicate right
                    while (left < right && amounts[right] == amounts[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        int[] amounts = {-5000, 3000, -1000, 2000, -3000, 5000, 1000};
        List<List<Integer>> triples = findOffsettingTriples(amounts);
        for (List<Integer> triple : triples) {
            System.out.println(triple);
        }
    }
}

[-5000, 2000, 3000]
[-5000, -1000, 5000] (wait, let me recalculate...)

Where exactly do you skip duplicates?

Duplicate skipping happens at three places, and getting all three right is what distinguishes a correct solution from one that emits duplicates.

1. Fixed element (outer loop): if amounts[i] == amounts[i-1], skip, because fixing the same value again would regenerate the same triples.
2. Left pointer (after a match): advance left past equal values so you do not record the same triple again.
3. Right pointer (after a match): retreat right past equal values for the same reason.

// Skip 1: fixed element
if (i > 0 && amounts[i] == amounts[i - 1]) continue;

// Skip 2 and 3: after recording a valid triple
while (left < right && amounts[left] == amounts[left + 1]) left++;
while (left < right && amounts[right] == amounts[right - 1]) right--;
left++;
right--;

What is the early-exit optimisation?

Because the array is sorted, once the fixed element is greater than zero (when the target is zero), the smallest possible triple sum is the fixed element plus the two next-smallest elements, which are all non-negative or positive, so the sum can never reach zero. Breaking out of the outer loop prunes a lot of work on arrays with many positive values.

if (amounts[i] > 0) break;
// All remaining elements are >= amounts[i] > 0
// So amounts[i] + amounts[left] + amounts[right] > 0 always

How is this different from the brute-force approach?

The naive triple nested loop checks every combination of three elements, which is O(n cubed). The sort plus two-pointer approach reduces this to O(n squared), which is the accepted optimal for comparison-based 3Sum.

| Approach | Time | Space | Handles Duplicates |
|---|---|---|---|
| Triple loop | O(n cubed) | O(1) | Needs a Set |
| Sort + two-pointer | O(n squared) | O(1) | Skip duplicates naturally |
| Hash-based | O(n squared) | O(n) | Fiddly duplicate management |

// Brute force: O(n^3)
for (int i = 0; i < n; i++)
    for (int j = i+1; j < n; j++)
        for (int k = j+1; k < n; k++)
            if (a[i]+a[j]+a[k] == 0) /* record */;

What about BigDecimal for financial amounts?

For banking data, use BigDecimal and compareTo. Sorting BigDecimal uses natural order. Duplicate skipping uses compareTo(other) == 0 so scale differences do not create spurious distinct values. Sum comparison also uses compareTo.

package com.bank.dsa;

import java.math.BigDecimal;
import java.util.*;

public class BigDecimalThreeSum {
    public static List<List<BigDecimal>> threeSum(BigDecimal[] amounts) {
        Arrays.sort(amounts);
        List<List<BigDecimal>> result = new ArrayList<>();
        int n = amounts.length;
        for (int i = 0; i < n - 2; i++) {
            if (i > 0 && amounts[i].compareTo(amounts[i - 1]) == 0) continue;
            if (amounts[i].compareTo(BigDecimal.ZERO) > 0) break;
            int l = i + 1, r = n - 1;
            while (l < r) {
                BigDecimal sum = amounts[i].add(amounts[l]).add(amounts[r]);
                int cmp = sum.compareTo(BigDecimal.ZERO);
                if (cmp == 0) {
                    result.add(List.of(amounts[i], amounts[l], amounts[r]));
                    while (l < r && amounts[l].compareTo(amounts[l + 1]) == 0) l++;
                    while (l < r && amounts[r].compareTo(amounts[r - 1]) == 0) r--;
                    l++; r--;
                } else if (cmp < 0) l++;
                else r--;
            }
        }
        return result;
    }
}

What are common mistakes?

The most common mistake is missing one of the three duplicate-skip points, which produces repeated triples. Another is skipping duplicates incorrectly by checking amounts[left] == amounts[left - 1] instead of amounts[left] == amounts[left + 1] after a match, which can skip valid triples.

// Wrong: skip before advancing, may skip valid triple
while (left < right && amounts[left] == amounts[left - 1]) left++;

// Correct: skip forward past duplicates of the current match
while (left < right && amounts[left] == amounts[left + 1]) left++;
left++; // then advance past the last duplicate

What are edge cases?

Edge cases include arrays with fewer than three elements (return empty), arrays of all zeros (one triple [0, 0, 0]), and arrays where no triple sums to zero. The early-exit optimisation handles the case where the smallest fixed element is already positive.

threeSum(new int[]{});           // []
threeSum(new int[]{0});          // []
threeSum(new int[]{0, 0, 0});    // [[0, 0, 0]]
threeSum(new int[]{1, 2, 3});    // []

What should a senior engineer know?

A senior engineer explains the correctness argument for why the three duplicate skips are sufficient, not just that they work. They mention the early-exit pruning, the O(n squared) lower bound for comparison-based 3Sum, and the generalisation to kSum using recursion. They sort a copy of the input to leave the caller's array untouched in production code.