Place a slow pointer and a fast pointer
Updated
Slow/fast placement starts both at 0. Each step, slow += 1 and fast += 2. Fast races. Slow walks. You stop before fast leaves the array.
What to focus on
After k in-range steps, slow = k and fast = 2k. Both indices stay in 0..n-1 until the next fast += 2 would go out.
Worked examples
three
a = [4, 1, 9]- slow=0, fast=0
- one step: slow=1, fast=2
Result: slow=1, fast=2
four
a = [4, 1, 9, 1]- slow=0, fast=0
- one step: slow=1, fast=2
- next fast=4 is out of range
Result: slow=1, fast=2
one
a = [7]- slow=0, fast=0
- fast+=2 would be 2, illegal
Result: slow=0, fast=0 · no step
Try it
Write placeSlowFast(a). a is an array of integers. slow and fast are indices, both starting at 0. Each step: slow += 1, fast += 2. Print slow and fast after each in-range step. Never write fast out of range. On [4, 1, 9] after one step: slow=1, fast=2. On [4, 1, 9, 1, 7] after two steps: slow=2, fast=4. On [4, 1, 9, 1] stop at slow=1, fast=2.
a is nonempty. Length ≥ 3 so one slow/fast step is in range.