Build a map in linear time
Updated
n puts are expected O(n). That is how you build a frequency map, an index map, or a grouping in one pass. Nested loops that put from every pair are O(n²) puts — still expected O(1) each, total quadratic.
What to focus on
Do not rebuild the map inside an inner loop. Build once, query many.
Worked examples
one pass
a = [4, 1, 9, 1], freqMap- 4 puts
Result: expected O(n)
rebuild each i
a = [4, 1, 9], for each i rebuild freq of a[i+1..]- ~n² puts
Result: O(n²) — slide or prefix instead
empty
a = []- zero puts
Result: {} in O(1)
Try it
Write freqMap(a). a is an array of integers. Build the map in one left-to-right pass. Do not rebuild a suffix map at every index. a = [4, 1, 9, 1], freqMap → expected O(n). a = [4, 1, 9], for each i rebuild freq of a[i+1..] → O(n²) — slide or prefix instead. a = [] → {} in O(1).
a is a list of integers and may be empty.