Difference of two sequences with pointers
Updated
a − b: while both live, if a[i] < b[j] emit a[i] and i++ (in a not in b). If a[i] > b[j] then j++ (b has a value a does not). If equal, skip both (in both). Then drain leftover a, not leftover b.
What to focus on
Emitted values are in a and missing from b. Leftover b is ignored. Leftover a is all extra.
Worked examples
drop 4 and 9
a = [1, 4, 9], b = [4, 7, 9]- 1<4 emit 1
- 4==4 skip both
- 9==9 skip both
Result: [1]
keep the rest
a = [1, 4, 9], b = [4, 7]- emit 1
- skip 4
- 7<9 j++ then drain 9
Result: [1, 9]
nothing in b
a = [1, 4, 9], b = [7]- 1<7 emit 1
- 4<7 emit 4
- 9>7 j++ drain 9
Result: [1, 4, 9]
Try it
Write diff(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. Result is a − b. Return values in a missing from b. Do not print leftover b. For a = [1, 4, 9] vs b = [4, 7, 9] get [1]. Vs [4, 7] get [1, 9]. Vs [7] get [1, 4, 9].
a and b are nonempty and sorted non-decreasing.