Arrays and Hashing: Trading Memory for a Faster Lookup

Almost every array problem starts life as a nested loop. “For each element, look at every other element” — two fors, $O(n^2)$, and it passes the small test cases. The entire Arrays & Hashing category is really one move repeated: replacing that inner loop with a question you can ask a hash table in constant time.

Here’s the move on Two Sum. The nested-loop version asks “is there a later element that completes the pair?” by scanning forward. Swap the scan for a map:

Map<Integer, Integer> seen = new HashMap<>();   // value -> index
for (int i = 0; i < nums.length; i++) {
    int need = target - nums[i];
    if (seen.containsKey(need)) return new int[]{ seen.get(need), i };
    seen.put(nums[i], i);
}

The inner loop is gone. Each element asks the map “have I already seen the number that completes me?” — an expected $O(1)$ lookup instead of an $O(n)$ scan — and the whole thing drops to one pass. That trade, memory for lookup speed, is the pattern. The rest of this hub is about the two decisions it hangs on: what you store, and when the trade isn’t worth making.

What you actually store

Three shapes cover almost every problem in this category:

• A set, for “have I seen this?” Contains Duplicate is the whole idea: add as you go, and a failed insert means a repeat. Membership is all you need, so a Set beats a Map. Valid Sudoku is the same reflex in three directions at once — a seen-set for each row, each column, and each box.
• A count map, for “how many of each?” Valid Anagram is two count maps compared; Top K Frequent is one count map followed by bucketing the numbers by frequency — which, because frequencies run from 0 to n, sorts them in $O(n)$ without ever calling a comparison sort.
• A map keyed by a canonical form. Group Anagrams is the sharp one, and the one that finally taught me to look past the loop: the key isn’t the word, it’s its signature — the sorted letters, or a 26-slot count. Every anagram collapses to the same key, so the grouping falls out of the map for free.

When a problem in this category is genuinely hard, it’s almost never the table — it’s spotting the canonical key that makes two things which look different land in the same bucket.

When hashing is the wrong reflex

This is the part the category doesn’t advertise, and the reason “just use a hash map” is a reflex worth distrusting. Some of these problems are here precisely to test whether you’ll reach past the obvious hash solution.

• Product of Array Except Self looks like it wants a map, but the clean answer is a prefix and suffix sweep — one pass accumulating products from the left, one from the right — with no hashing and, pointedly, no division. The follow-up bans division specifically to push you off the lazy path.

• Longest Consecutive Sequence does use a set, but sorting is the trap: the trick is to dump everything in a set and only start counting from numbers whose predecessor is absent, so each element is visited once for an $O(n)$ result instead of $O(n \log n)$.

• Even Contains Duplicate has a quiet lesson — if the array is already sorted, a linear neighbor-scan beats a set outright, and if you can’t spare the $O(n)$ memory, sorting first and then scanning neighbors trades that space for an $O(n \log n)$ pass. The spoke walks through why “just use a hash set” isn’t automatic.

• Encode and Decode Strings isn’t a hashing problem at all — it’s serialization. Length-prefix each string so the decoder always knows where one ends and the next begins (4#code5#lines), and no map is involved; it rides in this category as an array-of-strings warm-up.

So the category is really two skills wearing one name: reach for the hash table fast, but recognize the handful of problems built to reward doing without it.

The cost of the trade

Hashing buys time with space, and the receipt is easy to read: a set or map turns an $O(n^2)$ pairwise scan into expected $O(n)$ time — hash lookups are average-case constant, not worst-case — at the price of $O(n)$ memory. Usually a bargain. It stops being one when memory is the constrained resource or when the input’s own structure — already sorted, bounded range, a cheap arithmetic relationship — hands you the answer without paying for a table.

That exact trade is why databases keep a hash index: paying storage to keep a key-to-row map turns a full-table scan into a single keyed lookup. The interview hash map and the database index are the same idea at different scales — spend memory so you never have to scan again. Seeing them as one thing made the “when is it worth it” question concrete for me: you index the lookups you’ll repeat, and scan the ones you won’t.

Two skills, one label

So the category splits in half. Most of it rewards keying the right thing and letting a constant-time lookup do the work a nested loop was doing. A stubborn minority — the prefix sweep, the sequence-start set, the length-prefixed decoder — is there to check you won’t reach for a map on reflex when the array’s own structure already hands you the answer. The first time Product of Array Except Self talked me out of the HashMap I’d half-typed, the category stopped being “use a hash map” and became “know whether to.”

Where these come from

The problem set is NeetCode’s Arrays & Hashing group. A couple of its members are deliberately non-hashing — Product of Array Except Self leans on prefix and suffix sweeps, and Encode and Decode Strings is really serialization.