Skip to main content

DSAPath14 mincore

Two Pointers

The two-pointer method moves two indices or references through data to exploit order, windows, or relative speed.

DifficultyCore
TierTier 2
ModulePointer Techniques
LanguagesPython

Why This Matters

Two pointers turn many nested-loop scans into linear passes. The technique is everywhere: sorted two-sum, partitioning, merging, sliding windows, linked-list cycle detection, and removing duplicates.

Core Idea

Use two moving positions that preserve an invariant.

PatternPointer meaningTypical problem
Opposite endsleft and right bound a search spacesorted two-sum
Same directionread and write positionscompaction, remove duplicates
Slow and fastdifferent speedscycle detection, middle node
Windowleft and right bound a valid intervalsubstring and subarray constraints

Non-Example or Failure Mode

Two pointers are not magic for unsorted data. Sorted two-sum works because moving left increases the sum and moving right decreases it. Without monotonic structure, the pointer moves may discard valid answers.

Worked Example

Sorted two-sum: find whether [1, 3, 4, 8, 10] contains two values that sum to 11.

left = 0, right = 4
1 + 10 = 11, found

If the sum is too small, move left right. If the sum is too large, move right left. The invariant is that discarded pairs cannot reach the target.

Common Mistakes

MistakeCorrection
Applying sorted two-sum to unsorted input.Sort first or use a hash table.
Moving both pointers every iteration.Move the pointer justified by the invariant.
Forgetting termination conditions.Use left < right or a window-specific invariant.
Treating sliding window as always valid.Some constraints are not monotone and need different tools.

Diagnostic Questions

Question typeQuestionAnswer signal
DefinitionWhat makes it two-pointer?Two positions move through the structure under an invariant.
Example / non-exampleWhy does sorted two-sum need sorted input?Pointer moves rely on monotonic sum changes.
ComputationWhat is the cost of opposite-end two-sum?O(n) after sorting or on already sorted input.
TransferHow does slow-fast differ from left-right?It uses speed difference, not opposite bounds.

Exercises

Beginner:

  • Run sorted two-sum by hand on six numbers.
  • Remove duplicates from a sorted array with read/write pointers.
  • Find the middle of a linked list with slow/fast pointers.

Intermediate:

  • Implement a sliding window for longest subarray with sum at most k when all numbers are nonnegative.
  • Explain when sorting plus two pointers beats a hash-table solution.

Challenge:

  • Prove why opposite-end two-sum does not discard a valid pair.

Diagram Recommendation

Type: pointer movement trace.

Caption: "Left and right pointers shrink the search interval."

Purpose: Make the invariant visible at every move.

Next Topics

References

  • Bentley. Programming Pearls (2nd ed., 2000). Array scanning patterns.
  • Skiena. The Algorithm Design Manual (3rd ed., 2020). Two-pointer and sorting-based patterns.