Recognize a same-direction trail
Updated
Same-direction: both pointers start on the left (or both on the head) and only increase. Read/write compact, sorted merge, fast/slow, k-gap on a list. The trail never steps backward.
What to focus on
w (or slow, or j) lags. i (or fast, or the lead) is the front. If one pointer started at n-1, it is opposite-end instead.
Worked examples
compact
a = [0, 1, 0, 9], i and w both grow- w lags i
- neither decreases
Result: same-direction
merge
a = [1, 4, 9], b = [4, 7, 9], i and j both grow- i starts 0, j starts 0
- each ++ on a smaller head
- neither ever decreases
Result: same-direction, two sequences
not this
a = [1, 4, 9], t=13, L=0 R=2- R starts at the end
- R--
Result: opposite-end
Try it
Write classify(a). a is an array of integers. Same-direction: both pointers start left and only increase. Opposite-end: R starts at n-1. Print same-direction trail or not. Return nothing. For a = [0, 1, 0, 9] compact, merge of [1, 4, 9] with [4, 7, 9], and two-sum on [1, 4, 9].
a is nonempty. Merge sequences are sorted. Pair-sum a is sorted.