Basic Hashing
EasyA tally you can query instantly
Problem
Use a hash map or frequency array to store and look up counts of items in O(1) average time.
Pre-count everything into a tally sheet so each 'how many?' question is answered in one look.
The idea
Walk the array once incrementing a counter per value, and every later 'how many of x?' question is answered in O(1). Building the tally costs one pass, which pays for itself the moment you have more than a couple of queries.
The trick
- One pass to build, O(1) per query — the win grows with the number of queries.
- For values in a known small range, index a plain array instead of hashing.
- Ask for a missing key and you should get 0, not a crash — use getOrDefault or a default dict.
This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.
Step 1 of 2. Here's the example — count of 2 in [1,2,2,3,2] Values: 1, 2, 2, 3, 2.
1freq = {}2for x in arr: freq[x] = freq.get(x,0)+13lookup freq[q]Input
- array
- [1, 2, 2, 3, 2]
Output
- answer
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [1, 2, 1, 3, 2], query = 2
- Output:
- 2
- Explanation:
- 2 appears twice — a hash tally answers instantly.
Example 2
- Input:
- nums = [5, 5, 5], query = 5
- Output:
- 3
- Explanation:
- 5 shows up three times.
Example 3
- Input:
- nums = [1, 2, 3], query = 9
- Output:
- 0
- Explanation:
- 9 isn't present → 0.
Finished the walkthrough? Add it to your streak.