Two-Pointer Merging & Interval Processing
Core idea: Give each of two sorted sequences its own pointer. Compare the two fronts, act on the smaller (emit it, or test it for overlap/closeness), and advance only the pointer you consumed. Each pointer crosses its list once, so two lists of size
nandmmerge in O(n + m) — no backtracking, ever.
The parallel-walk, in one picture
![Two sorted lists A=[2,5,9,13] and B=[1,6,8,14] walked in parallel by pointers i and j, comparing A[i] vs B[j] and advancing the smaller value](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/two-pointers/two-pointer-merging-intervals-diagram-1.svg)
![Compare-and-consume loop: A[i] and B[j] feed a compare; if A smaller consume A and i+=1, if B smaller consume B and j+=1, then loop back](https://maangioassets.blob.core.windows.net/diagrams/coding-interview/101/chapters/two-pointers/two-pointer-merging-intervals-diagram-2.svg)
This is the merge step of merge-sort — and the engine behind LSM-tree / SSTable compaction (Cassandra, RocksDB), merging sorted logs into one timeline in distributed tracing, and time-series alignment in Kafka/Flink/Spark pipelines. Two sorted inputs, one ordered output, linear time.
Sign in to continue reading
The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.
Sign in to read the full lesson