Extra space of two indices
Updated
L and R (or i and w) are two integers: O(1) extra. The input array is not extra. A hash of n keys is O(n) extra. An output of n merged values is output, not aux, if the caller requires it.
What to focus on
In-place compact: O(1) aux. Merge into a new array: O(n+m) output. Fast/slow on a list: two node pointers, O(1) aux.
Worked examples
in-place compact
a = [0, 1, 0, 9], i and w- two ints
- mutates a
Result: O(1) aux
sorted two-sum
a = [1, 4, 9], L and R- two ints
- no hash
Result: O(1) aux
hash two-sum
a = [4, 1, 9], t=10, seen set- insert 4,1,9
- set size 3
Result: O(n) aux
Try it
Write auxSpace(a). a is an array of integers. L and R (or i and w) are two indices: O(1) extra. A hash of n keys is O(n) extra. Print aux space for compact, sorted two-sum, and hash two-sum. Only the hash is O(n). For a = [0, 1, 0, 9] compact, a = [1, 4, 9] two-sum, and a = [4, 1, 9] hash two-sum.
a is nonempty. Sorted two-sum uses a sorted copy or already-sorted a. Hash two-sum may be unsorted.