Topic 2 of 20
Hash maps, frequency counting and prefix sums: the tools behind a third of all interview questions.
Arrays and strings are the raw material of most interview questions, and hashing is the single most useful tool for working with them. A hash map gives you average O(1) insert and lookup, which lets you trade a little memory for a huge drop in time: the O(n²) "check every pair" solution becomes a single O(n) pass that asks "have I seen what I need?".
The second big idea is the prefix sum. Precompute running totals once, and the sum of any subarray becomes one subtraction. Combine a prefix sum with a hash map ("how many earlier prefixes equal current − k?") and you can count subarrays with a target sum in linear time. This pattern reappears in 2D grids, in modular arithmetic and in balance problems.
Finally, practise in-place tricks: using the array's own indices as a hash, swapping elements into position, and reversing sections. They give O(1) extra space solutions that interviewers often ask for as a follow-up.
The most-asked interview problem ever; teaches the 'store the complement' idea behind countless solutions.
Shows the time-vs-space trade-off between sorting and hashing in its simplest form.
Counting characters with a fixed-size array is the base of every anagram and permutation problem.
Building a hash map yourself (buckets, collisions) makes the O(1) promise concrete.
A quick drill on comparing two frequency tables.
Two maps enforce a one-to-one mapping, a subtle bug trap interviewers use.
Same bijection idea applied across words instead of characters.
Left-to-right parsing with a look-ahead rule; a common phone-screen question.
Vertical scanning across strings; also the motivating example for tries.
Carry handling on a digit array, the same idea as adding big numbers.
Introduces an O(1)-space voting trick that surprises most candidates.
Left sum vs right sum is the gentlest introduction to prefix sums.
Precompute once, answer every range query in O(1): the core prefix-sum payoff.
Choosing a good hash key (sorted string or count tuple) is the whole problem.
Beats the O(n log n) sort with bucket sort; a favourite follow-up.
Prefix/suffix passes without division; a very frequent Amazon and Meta question.
Encoding row, column and box membership in sets; clean hashing of 2D data.
Starting only from sequence beginnings gives O(n); a classic 'think before you sort' problem.
Frequency counting followed by bucket ordering.
Extends voting to two candidates; tests whether you truly understood the trick.
Three reversals rotate in O(1) space, a reusable in-place trick.
Find-swap-reverse in place; asked often and easy to get subtly wrong.
Careful edge-case handling (signs, whitespace, overflow), exactly what interviewers watch for.
The canonical 'count prefixes equal to sum − k' problem; appears everywhere.
Prefix sums modulo k: the same pattern with a number-theory twist.
Mapping 0 to −1 turns a balance question into a prefix-sum question.
Extends prefix sums to grids with inclusion-exclusion.
Combining two structures to get O(1) for everything; a top design question.
Uses the array itself as a hash set for O(1) extra space.
Complement lookup with duplicate handling, a step up from Two Sum.
The hardest classic in-place trick (cyclic placement); asked at Google and Amazon.
Adds duplicates to the O(1) design, forcing careful index bookkeeping.
Collapses a 2D problem into many 1D 'subarray sum equals k' problems.
Pure implementation under pressure; a known Google and LinkedIn question.
Introduces the prefix function (KMP) for linear-time string matching.