Extra space of a hash map
Updated
A map with k keys is Θ(k) entries plus table overhead (buckets, load factor). Frequency of n items is O(min(n, distinct)) keys, not always O(n). The original array is separate unless you destroy it.
What to focus on
Nested maps add inner tables. Two-sum's map is extra Θ(n) in the worst case (all unique).
Worked examples
k keys
a = [4, 1, 9] as three pairs- k=3
Result: Θ(3) entries
freq of dups
a = [1, 1, 1, 1]- one key
Result: Θ(1) map on n=4
empty
a = []- no entries
Result: Θ(1) or empty table
Try it
Write extraSpace(kind). kind is "pairs", "freqDups", or "twoSum". Return the extra space in terms of distinct keys k, not always n. a = [4, 1, 9] as three pairs → Θ(3) entries. a = [1, 1, 1, 1] → Θ(1) map on n=4. a = [] → Θ(1) or empty table.
keys are integers. a may be empty.