CodeWithYash

Foundation · Module 6 · Lesson 4

Three-sum reduction

Fix one value, then solve a two-pointer subproblem.

15–25 min readLesson 35 of 123

Lesson 35 of 123

1d streak

Theory lesson · Step-by-step

Understand Three-sum reduction

Fix one value, then solve a two-pointer subproblem.

Worked approach

Trace the reasoning step by step

  1. 1Assign a precise meaning to both pointers in Three-sum reduction.
  2. 2Use ordering or a read/write contract to decide which pointer can move safely.
  3. 3Record a match or write a finalized value before moving past it.
  4. 4Move at least one pointer monotonically on every iteration.
  5. 5Test duplicates, crossing pointers, empty ranges, and all-equal values.

Concrete example

Find zero-sum triples in [-1,0,1,2,-1,-4].

  1. 1Sort to [-4,-1,-1,0,1,2].
  2. 2Fix -1 and search two ends for sum 1.
  3. 3Skip duplicate fixed values.

Unique triples are [-1,-1,2] and [-1,0,1].

What must remain true (Loop Invariant)

The region discarded by Three-sum reduction cannot contain an unexamined valid answer; each pointer move is justified by order or a finalized output position.

Cost Model

Complexity & Trade-offs

Sort and scan each fixed value
O(n²)
O(1) excluding sort
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Sorted pair search, compaction, merging, partitioning, and palindrome checks.
  • Replacing nested loops when boundaries move monotonically.
  • Maintaining disjoint processed and candidate regions.

Common mistakes

  • Moving a pointer without proving the discarded region is impossible.
  • Forgetting duplicate skipping in enumeration problems.
  • Applying an order-dependent pointer rule to unsorted data.

Practice prompts

  • Reproduce the worked Three-sum reduction example without looking at the trace.
  • Change one input condition and explain whether the Three-sum reduction invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.