Draw both indices after each move
Updated
After every L++ / R-- / i++ / w++, write the pair (L, R) or (i, w) and the two values. A trace is the sequence of those pairs, not a paragraph.
What to focus on
If you cannot name both indices, you did not finish the step. Draw on the array, then move, then draw again.
Worked examples
two-sum
a = [1, 4, 9], t=13, L=0 R=2- (0,2) 1+9=10 too small, L++
- (1,2) 4+9=13 hit
Result: (1, 2) values 4, 9
compact
a = [0, 1, 0, 9], keep nonzero, i=0 w=0- (0,0) drop, i++
- (1,0) write, w++
- (2,1) drop, i++
- (3,1) write, w++
Result: end i=4 w=2
inward miss
a = [1, 4, 9], t=8, L=0 R=2- (0,2) 1+9=10 too big, R--
- (0,1) 1+4=5 too small, L++
- (1,1) L==R stop
Result: no pair, last draw (1, 1)
Try it
Write trace(a). a is an array of integers. L and R are opposite-end indices for pair-sum. i and w are same-direction indices for compact. Print (L, R, a[L], a[R]) each step for two-sum, then (i, w) for compact. Return nothing. Two-sum t=13 and t=8 on [1, 4, 9]. Compact on [0, 1, 0, 9].
a is nonempty. For pair-sum a is sorted non-decreasing, length ≥ 2.