Three Sum Problem All Unique Triplets in DSA C - Deep Dive

Overview - Three Sum Problem All Unique Triplets

What is it?

Given an integer array, find all unique triplets (a, b, c) such that a + b + c = 0. No duplicate triplets should appear in the result. The optimal solution sorts the array, then uses a fixed pointer and two-pointer scan to find pairs that complete each triplet in O(n²) time.

Why it matters

Three Sum is a canonical two-pointer problem that extends Two Sum to three elements. It demonstrates how sorting enables O(n) pair-finding, how to skip duplicates without a hash set, and how the two-pointer technique reduces a potentially O(n³) brute-force to O(n²). In C, managing the result collection requires careful dynamic array or fixed-size array handling.

Where it fits

You need comfort with C arrays, sorting (qsort), and the two-pointer technique before tackling this. After mastering it, Four Sum, Three Sum Closest, and Container With Most Water follow naturally.

Mental Model

Core Idea

Fix one element (nums[i]), then find pairs in the remaining sorted subarray that sum to -nums[i] using left and right pointers.

Think of it like...

Looking for three weights on a balance scale that sum to zero. Sort all weights. Pick one weight, then slide two fingers (left and right) through the remaining weights until they balance.

Sorted: [-4, -1, -1, 0, 1, 2]

i=0 (a=-4): need b+c=4. L=1,R=5: -1+2=1<4 → L++.
             L=2,R=5: -1+2=1<4 → L++. L=3,R=5: 0+2=2<4 → L++.
             L=4,R=5: 1+2=3<4 → L++. L=R → stop.

i=1 (a=-1): need b+c=1. L=2,R=5: -1+2=1=1 → FOUND [-1,-1,2]. Skip dupes.
             L=3,R=4: 0+1=1=1 → FOUND [-1,0,1]. Skip dupes. L=R → stop.

i=2 (a=-1): duplicate of i=1 → SKIP.

i=3 (a=0): need b+c=0. L=4,R=5: 1+2=3>0 → R--. L=R → stop.

Result: [[-1,-1,2], [-1,0,1]]

Build-Up - 5 Steps

1

Foundation

Why Sort First

Concept: Sorting enables two-pointer and duplicate skipping in O(1) per step.

Without sorting: finding pairs that sum to a target requires O(n) scan per position = O(n²) per fixed element = O(n³) total. With sorting: two-pointer finds all pairs in O(n) per fixed element = O(n²) total. Duplicate skipping: after sorting, duplicates are adjacent. Skip nums[i] == nums[i-1] to avoid duplicate triplets without a hash set. In C: sort with qsort and a comparison function: int cmp(const void* a, const void* b) { return (*(int*)a - *(int*)b); } qsort(nums, n, sizeof(int), cmp);

Result

Sorting reduces the problem from O(n³) to O(n²) and enables O(1) duplicate detection.

Sorting is the key insight — it transforms a hash-based problem into a pointer-based problem, avoiding extra memory for a hash set.

2

Foundation

Outer Loop — Fix One Element

Concept: For each nums[i], find pairs in nums[i+1..n-1] that sum to -nums[i].

for (int i = 0; i < n - 2; i++). Two optimizations: (1) if nums[i] > 0, all remaining elements are positive (sorted), so no triplet can sum to 0 — break early. (2) if i > 0 && nums[i] == nums[i-1], skip this iteration to avoid duplicate triplets with the same first element.

Result

Outer loop selects each unique candidate for the first triplet element.

The early break when nums[i] > 0 is a powerful optimization — in a sorted array, positive first element means the sum can only be positive.

3

Intermediate

Two-Pointer Inner Search

🤔Before reading on: given sorted array with i fixed, how do you decide whether to move left pointer right or right pointer left? Commit to your answer.

Concept: Left pointer starts at i+1, right at n-1. Sum < 0 → L++. Sum > 0 → R--. Sum == 0 → record and move both.

int left = i + 1, right = n - 1. while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) left++; else if (sum > 0) right--; else { // Found triplet — record [nums[i], nums[left], nums[right]]. Move both: left++; right--. // Skip duplicates: while (left

Result

O(n) inner scan finds all triplets for a fixed i.

When sum > 0 in a sorted array, the only way to decrease the sum is to move R left (smaller value). When sum < 0, move L right. This eliminates one element per step.

4

Intermediate

Duplicate Skipping — Both Levels

🤔Before reading on: where must duplicate skipping happen — only in the outer loop, only inner, or both? Commit your answer.

Concept: Skip outer duplicates (same i values) and inner duplicates (same left/right values after finding a triplet).

Outer: if (i > 0 && nums[i] == nums[i-1]) continue. Inner after match: while (left < right && nums[left] == nums[left-1]) left++; while (left < right && nums[right] == nums[right+1]) right--. Both are needed: outer prevents duplicate first elements, inner prevents duplicate pairs. Note: skip AFTER moving left/right once (skip nums[left-1] not nums[left]) to correctly advance past the duplicate.

Result

All duplicate triplets eliminated without a hash set.

In C, duplicate skipping by sorted-order adjacency check is more cache-friendly and uses O(1) memory compared to a hash set approach.

5

Advanced

Result Collection in C — Fixed Array

🤔Before reading on: how many triplets can there be at maximum for an array of n elements? Commit your estimate.

Concept: In C, results must be collected in a pre-allocated 2D array. Max triplets is O(n²/6) but in practice much less.

Pre-allocate: int result[MAX_TRIPLETS][3] and int count = 0. When a triplet is found: result[count][0] = nums[i]; result[count][1] = nums[left]; result[count][2] = nums[right]; count++. For the given constraints (n ≤ 3000), MAX_TRIPLETS = 1000 is safe. Return count via pointer parameter or as return value. This avoids dynamic memory allocation complexity in C.

Result

Simple fixed array collection handles all practical inputs.

C's lack of built-in dynamic containers makes result collection more explicit. Fixed array with a count is the idiomatic C approach for bounded results.

Under the Hood

Sorting: O(n log n). Outer loop: O(n) iterations. Inner two-pointer: O(n) per outer iteration. Total: O(n²). Each element is pointed to by L or R at most once per outer iteration — the two pointers together traverse at most n steps. Duplicate skipping is O(1) amortized per duplicate since each element is skipped at most once.

Why designed this way?

The two-pointer technique works because of the sorted order invariant: moving L right increases the sum, moving R left decreases it. This binary search-like monotonicity allows O(1) decision per step instead of O(n) scan. The duplicate skipping leverages adjacency in sorted order — a property unavailable without sorting.

[-4, -1, -1, 0, 1, 2], i=1 (a=-1), target=1

 i     L              R
[-4, -1, -1, 0, 1, 2]
      1   2  3  4  5   (indices)

Step 1: L=2, R=5: -1+2=1=target → MATCH! Record [-1,-1,2].
Skip dup L: nums[2]=-1, nums[3]=0 ≠ nums[2], stop.
Skip dup R: nums[5]=2, nums[4]=1 ≠ nums[5], stop.
L=3, R=4.

Step 2: L=3, R=4: 0+1=1=target → MATCH! Record [-1,0,1].
L=4=R → stop inner loop.

Myth Busters - 2 Common Misconceptions

Quick: do you need a hash set to eliminate duplicate triplets in the two-pointer approach? Commit yes or no.

Common Belief: A hash set is needed to check if a triplet was already found.

Reality: No hash set needed. Sorting makes duplicates adjacent. Skip nums[i] == nums[i-1] in outer loop and skip same left/right values after finding a triplet. The sorted order guarantees no duplicate triplet can be produced.

Why it matters: A hash set would add O(n) space and O(n) hash computation per triplet. Sorted duplicate skipping is O(1) per skip and O(1) space.

Quick: when skipping inner duplicates after a match, should you compare nums[left] with nums[left-1] or nums[left+1]? Commit your answer.

Common Belief: Skip forward: while nums[left] == nums[left+1], left++.

Reality: Skip backward: after moving left++, check while nums[left] == nums[left-1]. This skips over duplicates of the just-matched value correctly.

Why it matters: Comparing with nums[left+1] stops one position too early or can skip too far, missing valid non-duplicate values.

Expert Zone

1

The early break when nums[i] > 0 is valid only because the array is sorted. Don't use it before sorting.

2

For i == 0, the duplicate skip condition i > 0 && nums[i] == nums[i-1] correctly doesn't skip i=0 even if nums[0] == nums[1], because we haven't processed i=0 yet.

3

In C, the qsort comparison function returning (a - b) can overflow for extreme int values. Use: return (a > b) - (a < b) for safety.

When NOT to use

If you need to find the triplet closest to zero (not exactly zero), use a different approach — track minimum absolute difference instead of exact zero match. If duplicates are allowed in output (rare variant), remove the duplicate-skipping steps.

Production Patterns

Three Sum appears in computational geometry (finding collinear points), chemistry (finding molecular combinations), and financial analysis (finding zero-net portfolios). The two-pointer extension appears in K-sum problems — each additional element adds one more outer loop, giving O(n^(k-1)) for k-sum.

Connections

Two Sum Problem

Three Sum extends Two Sum: fix one element, find a Two Sum pair in the remaining array. The two-pointer inner loop is Two Sum on a sorted array.

Three Sum = for each element, solve Two Sum on sorted remainder. Four Sum = for each pair, solve Two Sum. This recursive extension works for any k-sum.

Two Pointer Technique

The inner loop is a textbook two-pointer application — opposing pointers converging toward each other based on sum comparison.

The sorted order invariant (moving L increases sum, moving R decreases sum) is what makes two-pointer O(n) — it's binary-search thinking applied to a pair.

Common Pitfalls

#1 Not skipping duplicates in the outer loop, producing duplicate triplets.

Wrong approach:

for (int i = 0; i < n - 2; i++) {
// No duplicate check — produces duplicate triplets for repeated nums[i]
int left = i + 1, right = n - 1;

Correct approach:

for (int i = 0; i < n - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // Skip duplicate first element
int left = i + 1, right = n - 1;

Root cause:

Without skipping, two iterations with nums[i] = -1 both find the same pairs, producing duplicate triplets like [-1,-1,2] twice.

#2 Comparing inner duplicates incorrectly — wrong direction.

Wrong approach:

// After match:
left++; right--;
while (left < right && nums[left] == nums[left + 1]) left++; // WRONG direction
while (left < right && nums[right] == nums[right - 1]) right--;

Correct approach:

// After match:
left++; right--;
while (left < right && nums[left] == nums[left - 1]) left++; // Compare with previous
while (left < right && nums[right] == nums[right + 1]) right--;

Root cause:

After left++, nums[left-1] is the value we just processed. Skip if current matches it. Comparing with left+1 looks ahead incorrectly.

Key Takeaways

Sort first — enables two-pointer O(n) pair search and O(1) duplicate detection.

Fix one element with outer loop, find complementary pair with two-pointer inner loop.

Skip outer duplicates: if i > 0 && nums[i] == nums[i-1] → continue.

After a match, move both pointers and skip inner duplicates comparing with previous value.

Early break: if nums[i] > 0 in sorted array, no triplet can sum to 0 — break outer loop.