unbuffered▌

Traverse & partition

seedling|planted |dsainterview-prepfamily|2.9 KB

The Traverse & partition family walks one or two cursors across a linear structure under a discard rule, so every element is settled in a single pass instead of a nested rescan — the family that turns O(n²) pair-and-partition work into O(n). The shared idea: whatever a cursor moves past is decided and never revisited, so state stays O(1) or a single map. It is the first family of Layer 1 in the DSA patterns hub.

Choosing within the family

  • Sorted input, and you need a pair / triple / sum to a target → opposing two pointers (converge from both ends).
  • Filtering, de-duping, or partitioning in place → same-direction two pointers (a slow write cursor trailing a fast read cursor).
  • A linked list cycle or midpoint in O(1) space → fast / slow pointers.
  • No order to exploit — you need seen-state or counts → hashing; and when the values are a permutation of 1..n, → cyclic sort.

Sub-techniques

  • Opposing two pointers — two cursors converge from the ends of a sorted range; each comparison discards one side. Two Sum II, Container With Most Water, 3Sum.
  • Same-direction two pointers — a slow write pointer trails a fast read pointer to compact or partition in place. Remove Duplicates, Move Zeroes, Sort Colors.
  • Fast / slow pointers — two cursors at different speeds meet inside a cycle or land on the midpoint, using no extra memory. Linked List Cycle, Middle of the List, Happy Number.
Hashing & frequency state — what collapses an O(n²) pair hunt into one pass?

A hash map trades space for O(1) recall: remember what you’ve already seen (or how often), so the partner of the current element is a single probe away instead of a rescan. The frequency-map variant counts occurrences — anagram grouping, or “subarray sum = k” via a running map of prefix sums.

Full note lands when I study this pattern.

Cyclic sort — how do you find the missing number in O(1) extra space?

When the values are a permutation of 1..n, each belongs at a known index, so you swap each element home in one pass — no hash set needed. Whatever ends up out of place is the missing or duplicated value. Missing Number, Find All Duplicates, First Missing Positive.

Full note lands when I study this pattern.

  • Sliding window — the same-direction two-pointer case where the gap between the cursors is the window you measure.
  • Binary search — also bounds a range from two sides, but halves on a monotone predicate instead of stepping one index at a time.
  • In production: two converging cursors over sorted runs is a merge — LSM-tree compaction and sorted-merge stream joins advance whichever side is behind, never revisiting what a cursor has passed.