Arrays and Hashing

TL;DR: The hash map gives you average O(1) insert and lookup, and that single property is what collapses an O(n^2) all-pairs scan into one O(n) pass. Two patterns cover most array problems: the seen-set (as you walk the array, ask the map whether the thing you need has already appeared) and frequency counting (tally occurrences in one pass, then read the tally). When you catch yourself about to write a nested loop over the same array, that is the cue to reach for a dictionary.

Why O(1) lookup changes the game

An array gives you O(1) access by index, but answering "is value x in here?" by scanning is O(n). Do 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 to a bucket directly, so the membership question no longer costs a scan. Replace the inner loop with a map lookup and the whole thing becomes O(n) time at the cost of O(n) extra space. That space-for-time trade is the entire trick, and naming it out loud in an interview is worth 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.