Arrays and Hashing

TL;DR: The hash map hands you average O(1) insert and lookup, and that one property is what folds an O(n^2) all-pairs scan into a single O(n) pass. Two patterns handle most array problems: the seen-set (as you walk the array, ask the map whether what you need has already shown up) and frequency counting (tally occurrences in one pass, then read the tally back). The moment you notice yourself about to write a nested loop over the same array, that is your cue to grab a dictionary.

Why O(1) lookup changes the game

An array hands you O(1) access by index, but answering "is value x in here?" through a scan costs O(n). Run that scan inside a loop over the array and you have an O(n^2) algorithm: fine for 100 elements, a disaster at a million. A hash map answers "have I seen x?" in average O(1) by hashing the key straight to a bucket, so the membership question no longer requires a scan. Swap the inner loop for a map lookup and the whole thing drops to O(n) time at the cost of O(n) extra space. That space-for-time trade is the whole trick, and saying it out loud in an interview earns a point.

The two-sum / seen-set pattern

Classic problem: given an array and a target, find two numbers that sum to the target. The naive answer checks every pair, O(n^2). The hash-map answer makes one pass and, for each number x, asks whether its complement target - x is already in the map.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:     # complement already passed?
            return [seen[target - x], i]
        seen[x] = i                # remember x for future lookups
    return []                      # no pair found

The invariant: seen holds every element to the left of the current index. You never need a pair you have not yet reached, because that pair will be found when its second element becomes the current one. One pass, O(n) time, O(n) space. The same shape solves "does any subarray sum to k" (store prefix sums), "find the first duplicate" (store values), and "are these two arrays disjoint" (build a set from one, probe with the other).

Frequency counting

The second pattern tallies things. Count occurrences in one pass, then answer questions by reading the counts: most frequent element, first non-repeating character, whether two strings are anagrams (compare their letter-count maps). Python's collections.Counter is this in one line. The point is that the tally is built in O(n) and every subsequent question is O(1) or O(k) on the distinct keys, instead of re-scanning per query.

Collisions and load factor

Two keys can hash to the same bucket, a collision. Real hash maps handle this with chaining (a list per bucket) or open addressing (probe to the next slot). The load factor is entries divided by buckets; as it climbs, collisions rise and lookups drift from O(1) toward O(n) in the worst case. Implementations keep it bounded (Python and Java resize and rehash once it crosses a threshold, often around 0.7), which is why O(1) is average, not guaranteed. You rarely tune this in interviews, but knowing it explains why "O(1)" comes with an asterisk and why an adversary feeding worst-case keys can degrade a naive map.

Why interviewers probe this

Arrays-and-hashing is the warm-up that filters for fluency. The interviewer is screening whether you instinctively trade space for time instead of writing the nested loop. The strong-answer move is to state the naive complexity, name the hash map, and explain the invariant ("the map holds everything to my left") before you code. The held-back follow-up is usually about the cost: "what is the space complexity, and what happens in the worst case?" If you can say O(n) space and explain that collisions make O(1) an average rather than a guarantee, you have shown depth past memorized templates.

Common misconceptions

• "Hash-map lookup is always O(1)." It is O(1) average. Worst case with pathological collisions is O(n); a high load factor degrades it.
• "A set and a dict are different tools." A set is just a map with no values. Use a set when you only need membership, a dict when you need to store an index or count alongside.
• "You must sort first to find pairs." Sorting is O(n log n) and often unnecessary; a single hash-map pass is O(n) and keeps the original order.
• "Frequency counting needs two passes." You can often tally and answer in the same pass (as in two-sum), checking the map before you insert the current element.

Key takeaways

• The hash map's average O(1) lookup is what turns an O(n^2) pair-scan into an O(n) pass.
• Seen-set: keep a map of everything to your left, then ask whether the complement you need is already there.
• Frequency counting: tally once in O(n), answer every later question cheaply.
• O(1) is average; collisions and load factor make the worst case O(n), which is why maps resize and rehash.