Scan from right for a misplace
Updated
From R, while L ≤ R and a[R] should stay on the right, R--. Stop on the first a[R] that should sit on the left, or when R passes L.
What to focus on
R only decreases. After the scan, either R < L (done) or a[R] is a right-side offender.
Worked examples
skip a 9
a = [0, 1, 0, 9], zeros left, L=1 R=3- a[3]=9 stays right
- R 3→2
- a[2]=0 should be left
Result: R=2 misplace 0
skip odds
a = [4, 1, 9], evens left, L=1 R=2- a[2]=9 odd stays right
- R 2→1
- a[1]=1 odd, still right, R 1→0
Result: R=0 holds 4, a left-side even
none
a = [0, 0, 1, 9], zeros left, L=2 R=3- a[3]=9 stays right, R--
- a[2]=1 stays right, R--
- R=1 < L=2, stop
Result: no right misplace
Try it
Write scanRightMisplace(a, L, R). a is an array of integers. L is the left index. R is the right index. R only decreases. Return R. The scan does not swap. Zeros-left on [0, 1, 0, 9] starting R=3. Evens-left on [4, 1, 9]. Zeros-left on [0, 0, 1, 9].
a is nonempty. L and R are in-range with L ≤ R. A right-side offender exists in [L, R], or R walks down onto a left-side value.