Intersect two sequences with pointers
Updated
While both live: if a[i] < b[j] then i++; if b[j] < a[i] then j++; if equal, emit once, i++, j++. Skip extra copies if you want unique output.
What to focus on
A value appears in the intersection only when both heads match. Advancing the smaller head discards a value that cannot pair.
Worked examples
two hits
a = [1, 4, 9], b = [4, 7, 9]- 1<4 i++
- 4==4 emit 4 both++
- 9==9 emit 9 both++
Result: [4, 9]
one hit
a = [1, 4, 9], b = [4, 7]- 1<4 i++
- 4==4 emit 4
- 9>7 j++ then j done
Result: [4]
all match
a = [1, 4, 9], b = [1, 4, 9]- 1==1 emit 1 both++
- 4==4 emit 4 both++
- 9==9 emit 9 both++
Result: [1, 4, 9]
Try it
Write intersect(a, b). a is a sorted array of integers. b is a second sorted array. i is the index on a. j is the index on b. Emit when heads match. Return the intersection. Run [1, 4, 9] vs [4, 7, 9], vs [4, 7], vs [1, 4, 9].
a and b are nonempty and sorted non-decreasing. The intersection is nonempty.