Arrays and Hashing

AI Generated

Hashing trades memory for time: a dictionary or set turns "have I seen this before?" from an $O(n)$ scan into an $O(1)$ lookup, which collapses a nested loop into a single pass.

The recurring tricks:

• Frequency map — count occurrences first, then read the counts back (anagrams, top-K, majority element).
• Prefix sums — store the running sum in a map as you go. A subarray summing to k ends at i wherever currSum - k was seen before. The same idea works with prefix XOR.
• Seen set — O(1) membership, so you can test neighbours instead of sorting (longest consecutive sequence).
• The array as the table — when the values are bounded, write the marker into the array itself and keep the space at O(1).

Sorting is the fallback when order matters more than counts, but it costs the $O(n \log n)$ that hashing was there to avoid.