Pick a tree map when keys must stay sorted
Updated
A hash map will not give you keys in sorted order. If you need smallest key, a range of keys, or in-order scan, sort the keys after (O(k log k)) or use a tree map from the start.
What to focus on
Lucky iteration that looked sorted is not an API. Sweep lines, next larger key, and streaming medians of keys are not hash-map iteration.
Worked examples
must sort
a = [9, 1, 4] as keys of a map- hash order unknown
- sort → 1,4,9
Result: extra sort, or a tree map
min key
a = [9, 1, 4] as {9:1, 1:1, 4:1}, ask min key- cannot peek a hash min in O(1)
Result: scan O(k) or tree
empty
a = []- no keys to sort
Result: {}
Try it
Write sortedKeys(m). m is a hash map whose keys are integers. Do not assume hash iteration is sorted. Return keys in sorted order by sorting them, or say to use a tree map. a = [9, 1, 4] as keys of a map → extra sort, or a tree map. a = [9, 1, 4] as {9:1, 1:1, 4:1}, ask min key → scan O(k) or tree. a = [] → {}.
Empty is in the cases. Keys are integers.