Recognize an O(n) two-pointer scan
Updated
If each pointer only moves forward (or only inward) and never resets, each index is visited O(1) times: O(n) time. Compact, merge, sorted two-sum, and lockstep list walks are this shape.
What to focus on
Count pointer increments. i goes 0..n at most once. L++ at most n, R-- at most n. That is ≤ 2n moves, not n².
Worked examples
compact
a = [0, 1, 0, 9], keep nonzero- i = 4 increments
- w = 2 increments
Result: 6 moves, O(n)
two-sum sorted
a = [1, 4, 9], t=13- L++ once, R stays
- 2 index reads
Result: O(n) on n=3
merge
a = [1, 4, 9], b = [4, 7, 9]- i ends at 3, j ends at 3
- 6 advances
Result: O(n+m)
Try it
Write countMoves(a). a is an array of integers. Pair-sum a is sorted. Merge sequences are sorted. Each pointer never resets. Print the move count for compact, two-sum, and merge. All are O(n). Compact on [0, 1, 0, 9], two-sum t=13 on [1, 4, 9], merge of [1, 4, 9] with [4, 7, 9].
a is nonempty. Pair-sum a is sorted. Merge sequences are sorted.