Meet in the middle to partition
Updated
L starts at 0, R at n-1. Hunt a left misplace and a right misplace, swap, then close in. Stop when L and R meet or cross. The meeting index is the split.
What to focus on
After the loop, every index < split satisfies the left predicate. Every index > split satisfies the right. The inner slice is gone.
Worked examples
zeros left
a = [0, 1, 0, 9], zeros left of nonzeros- L=1 holds 1, R=2 holds 0
- swap → [0, 0, 1, 9]
- L=2 R=1 cross
Result: split 2, left [0, 0]
evens left
a = [4, 1, 9], evens left of odds- L=1 holds 1 odd, R=2 holds 9 odd then R=1
- L and R meet at 1, no swap
Result: split 1, left [4]
already split
a = [0, 1, 9], zeros left- L=0 a[0]=0 stays, L++
- R=2 a[2]=9 stays, R--
- L=1 R=1 meet, no swap
Result: split 1
Try it
Write partitionMeet(a). a is an array of integers. L is the left index, start 0. R is the right index, start n-1. The left/right rules partition the values. Return the split index. Zeros left on [0, 1, 0, 9]. Evens left on [4, 1, 9].
a is nonempty, length ≥ 2. The left/right rules partition the values.