3Sum with Duplicate Skipping Explained: Tracing [-1, 0, 1, 2, -1, -4]

Imagine you are handed the unsorted array $\text{nums}=[-1,0,1,2,-1,-4]$ and asked to find every unique triplet $\{a,b,c\}$ that sums to 0. Your target is clear: find all combinations where $a+b+c=0$. For our working example, the expected result is $[[-1,-1,2],[-1,0,1]]$.

If you approach this with a naive triple-nested loop, you will test every possible combination of indices $(i,j,k)$. For an array of length 6, that means checking 20 different index triplets. Worse yet, because the array contains duplicate numbers like $-1$, a brute-force filter will produce redundant outputs such as $[-1,0,1]$ multiple times depending on which index of $-1$ was picked first.

Filtering duplicates after finding every combination creates massive memory overhead and wastes CPU cycles. We need a systematic way to bypass redundant work during the search, transforming an expensive combinatorial hunt into an ordered traversal.

nums = [-1, 0, 1, 2, -1, -4]
# Target: find all unique [a, b, c] such that a + b + c == 0
# Expected Output: [[-1, -1, 2], [-1, 0, 1]]

When we look at our locked working example $\text{nums}=[-1,0,1,2,-1,-4]$, the combinatorial chaos of checking every possible trio of indices immediately hits a wall. How do we eliminate redundant work without missing valid solutions? The answer is to impose order. If we sort the array first, identical values land adjacent to each other, turning a chaotic search space into a predictable runway.

Sorting transforms the raw input $\text{nums}=[-1,0,1,2,-1,-4]$ into $\text{sorted}=[-4,-1,-1,0,1,2]$. Now, instead of three nested loops, we fix one number at index $i$ and use a converging two-pointer approach for the remaining two numbers. Let pointer $L$ start immediately after $i$, and pointer $R$ start at the very end of the array. As we evaluate the sum $\text{nums}[i]+\text{nums}[L]+\text{nums}[R]$, we either need a larger sum (so we increment $L$) or a smaller sum (so we decrement $R$).

This sorted layout is what makes duplicate skipping mathematically trivial. If our fixed anchor $\text{nums}[i]$ is identical to the previous anchor $\text{nums}[i-1]$, we know instantly that any triplet we could form with it would be a duplicate of the ones we already generated. The same logic applies once we find a valid triplet: we must advance $L$ and $R$ past any duplicate numbers before looking for the next pair.

To see sorting and duplicate skipping in action, let us process our locked array: $\text{nums}=[-1,0,1,2,-1,-4]$. Our goal is to find all unique triplets that sum to 0.

Given:
- Array $\text{nums}=[-1,0,1,2,-1,-4]$
- Target sum $=0$

Steps:
1. Sort the array: Rearrange $\text{nums}$ in ascending order so that identical values sit adjacent to each other.
Sorted array: $[-4,-1,-1,0,1,2]$.
2. Iterate with pointer $i$: We fix $i$ at index 0 where $\text{nums}[0]=-4$. We set left pointer $L=1$ (value $-1$) and right pointer $R=5$ (value 2).
- Sum: $-4+(-1)+2=-3$. Since $-3<0$, we need a larger sum, so we increment $L$ ($L$ moves to index 2).
- Next sum: $-4+(-1)+2=-3$. Increment $L$ to index 3 (0). Sum becomes $-2$. Increment $L$ to index 4 (1). Sum becomes $-3$. Increment $L$ to index 5 (2). $L$ meets $R$, ending this $i$ loop.
3. Advance $i$ to index 1: $\text{nums}[1]=-1$. Set $L=2$ (value $-1$) and $R=5$ (value 2).
- Sum: $-1+(-1)+2=0$. Hit! We record the triplet $[-1,-1,2]$.
- Now, shrink the window and skip duplicates: increment $L$ while $\text{nums}[L]==\text{nums}[L-1]$ and decrement $R$ while $\text{nums}[R]==\text{nums}[R+1]$. $L$ moves to index 3 (0), $R$ moves to index 4 (1).
4. Continue with $i$ at index 2: $\text{nums}[2]=-1$. Because $\text{nums}[2]==\text{nums}[1]$, our duplicate-skipping check for $i$ (if i > 0 and nums[i] == nums[i-1]: continue) immediately skips this iteration to prevent duplicate triplets.
5. Advance $i$ to index 3: $\text{nums}[3]=0$. Set $L=4$ (value 1) and $R=5$ (value 2).
- Sum: $0+1+2=3$. Too large, decrement $R$.

Result:
Returning the collected unique triplets yields $\text{[[-1, -1, 2], [-1, 0, 1]]}$.

Try this: Trace the exact pointer movements and sums when i reaches index 3 (value 0) in the sorted array [-4, -1, -1, 0, 1, 2]. Why does this iteration fail to find a valid triplet?

Now that you have traced the original array $\text{nums}=[-1,0,1,2,-1,-4]$ through its sorted state and pointer jumps, let us test your mental model on a closely related variation. Consider a modified input array where duplicates are clustered differently: $\text{nums}=[-2,-2,0,0,2,2]$. We are still searching for unique triplets that sum to 0.

Work through the first major iteration of the algorithm manually. After sorting the array, our fixed outer pointer $i$ sits at the first element, and the inner left and right pointers bound the remaining window. Trace how many duplicate-skipping loops execute when the first valid triplet is found and how the pointers advance before examining the next distinct value of $i$.

def practice_trace_check():
    # Given nums = [-2, -2, 0, 0, 2, 2], target = 0
    # Sorted: [-2, -2, 0, 0, 2, 2]
    # If i = 0 (nums[i] = -2), L = 1, R = 5 (-2 + 0 + 2 = 0)
    # Task: What are the exact indices of L and R after collecting this first triplet and skipping all duplicates?
    pass

The fundamental lesson from our work with [-1, 0, 1, 2, -1, -4] is that sorting transforms an unstructured search space into a linear stream where duplicates sit adjacent to one another. Whenever we encounter nums[i] == nums[i-1], skipping saves redundant work without sacrificing correctness. This exact invariant scales upward to higher-order sum problems, such as 4Sum, or can be adapted for interval-based subset searches.

Consider how you would tackle a modified variant where you need to find four numbers summing to a target 0. By nesting a second fixed pointer alongside the first and keeping the inner two pointers, the time complexity shifts from $O(N^2)$ to $O(N^3)$, but the duplicate-skipping logic remains completely identical.

Whenever you design algorithms involving combinations or subsets that require uniqueness, look for the sorting-plus-adjacent-skip pattern. It replaces expensive hash set lookups with efficient pointer scans.