Arrays & Hashing: The Pattern Behind 40% of Interviews

Why arrays dominate interviews

An array is contiguous memory with O(1) indexed access. Almost every data-structure question eventually reduces to scanning, indexing or grouping an array, which is exactly why interviewers keep returning to it.

The trap is treating each question as new. In practice there are four recurring shapes: frequency counting, complement lookup, prefix aggregation and sliding windows.

• Frequency counting — count occurrences in a hash map, then answer in one pass.
• Complement lookup — store what you have seen, ask what you still need.
• Prefix aggregation — precompute running sums so any range is O(1).
• Sliding window — grow the right edge, shrink the left edge on violation.

Pattern 1 — complement lookup

Two Sum is the canonical version: for every element, ask whether target minus that element has already been seen. A single hash map turns an O(n squared) scan into O(n).

The same trick powers pair-with-difference, subarray-sum-equals-k and count-of-nice-subarrays. The complement changes; the shape does not.

Pattern 2 — prefix sums

Precompute prefix[i] as the sum of everything before index i. Any range sum becomes prefix[r + 1] minus prefix[l], which makes repeated range queries free.

Combine prefix sums with a hash map and you can count subarrays with a given sum in one pass — one of the highest-frequency medium questions of the last three years.

Pattern 3 — sliding window

When the question mentions longest, shortest or at most K, reach for a window. Expand the right pointer, update the window state, and contract the left pointer while the constraint is violated.

Every element enters and leaves the window at most once, so the whole scan stays linear even though there are two nested loops in the code.

How to practise this week

Solve five questions per pattern rather than twenty random ones. After each solve, write one sentence naming the pattern — that sentence is what you will recall under interview pressure.