Skip to content

Volume ITechnology

4.4.0 — Arrays & Hashing: The Pattern ​

Recognition cue. The brute force is a nested loop where the inner loop asks a question about what you have already seen: "does this appear again", "have I got a matching value", "how many times has this occurred". That inner loop is a lookup, and a lookup belongs in a hash map.

The move. Replace O(n^2) with O(n) time and O(n) space. It is the single most common optimisation in the whole of Part 4.

The skill that separates the easy problems in this group from the hard ones is not using a map — it is choosing what to put in it. Sometimes the key is the value. Sometimes it is a derived fingerprint. Sometimes it is what you still need rather than what you have.

The four templates ​

python
# 1. Have I seen this?  → a set
seen = set()  # (1)
for x in nums:
    if x in seen: return True  # (2)
    seen.add(x)                       # (3) ← always check BEFORE inserting

# 2. How many of each?  → a map from value to count
count = Counter(items)                # (4) or: count[x] = count.get(x, 0) + 1

# 3. Group by a fingerprint I choose  → a map from key to list
groups = defaultdict(list)  # (5)
for x in items:
    groups[fingerprint(x)].append(x)  # (6) ← the whole problem is this line

# 4. Store what I NEED, not what I have  → a map from value to index
seen = {}  # (7)
for i, x in enumerate(nums):
    if (target - x) in seen: return [seen[target - x], i]  # (8)
    seen[x] = i  # (9)

The templates, line by line.

(1) Template 1 remembers every value seen so far. (2) Ask whether this value was seen before. (3) Only then add it. Adding first would make every value match itself.

(4) Template 2 counts each value. Counter builds a map from value to how many times it appears in one pass.

(5) Template 3 makes a map from a key to a list, creating empty lists automatically. (6) Put each item in the list for its fingerprint, a key that is equal exactly for items that belong together. Choosing that key is the real problem, as in 4.4.4.

(7) Template 4 maps each value to its position. (8) Work out the partner this value needs, and look it up. (9) If it is not there yet, remember this value, in case a later value needs it. This is 4.4.3 Two Sum.

Templates 1 and 4 look almost identical and are used for opposite reasons. Template 1 remembers what has happened. Template 4 anticipates what would complete an answer. Being able to say which one a problem needs, out loud, before writing anything, is most of the recognition skill.

The nine problems ​

#ProblemThe one insight
4.4.1Contains Duplicate ★A nested scan asking "have I seen this" is a set lookup
4.4.2Valid Anagram ★Anagram means equal counts; ordering is more work than counting
4.4.3Two Sum ★Do not search for a pair — compute the partner and look it up
4.4.4Group Anagrams ★Design a fingerprint; the map is bookkeeping
4.4.5Top K Frequent Elements ★A frequency cannot exceed n, so counts are array indices
4.4.6Encode and Decode Strings ★No separator is safe — prefix the length instead
4.4.7Product of Array Except Self ★Two passes in opposite directions replace a nested loop
4.4.8Valid SudokuName each group with an index; (r//3)*3 + c//3
4.4.9Longest Consecutive Sequence ★Walk only from run starts, and prove the result is linear

★ marks the Blind 75 subset.

The traps on this pattern ​

Checking after inserting. In Two Sum and Contains Duplicate, insert after the check, or an element matches itself.

Claiming O(1) space while using a map. A map over an unbounded alphabet is O(k). Only a fixed-size array over a bounded alphabet is O(1), and you should say which assumption you are making.

Mutable objects as keys. Python refuses a list as a dictionary key — TypeError: unhashable type — which is loud and easy to fix with tuple(...). JavaScript accepts an array as a Map key and compares it by identity, so every entry becomes unique and nothing ever matches, with no error at all. The silent failure is the dangerous one. Encode to a string or a number first, and keep a separator in the encoding.

Aliased containers. [[]] * n in Python and new Array(n).fill([]) in JavaScript create one container and n references to it. Use [[] for _ in range(n)] and Array.from({length: n}, () => []).

Using {} where you mean a map. A plain JavaScript object coerces keys to strings, so 1 and "1" collide, and it inherits toString, constructor and friends from the prototype, so obj["constructor"] returns something you never stored. Use Map when keys are data (Chapter 3.6.11 covers this and prototype pollution).

Sorting when counting would do. If you only need frequencies or a maximum, sorting is O(n \log n) for something a single pass gives you.

What the interviewer will push on ​

"Your solution uses O(n) extra space. Can you do it in O(1)?" Usually the true answer is "only by sorting, which costs O(n \log n) time and destroys the original indices". Then ask whether the input may be modified. Naming the trade is better than guessing.

"Is your hash lookup really O(1)?" It is O(1) expected. Adversarially chosen keys can force every value into one bucket and degrade a lookup to O(n); real runtimes defend against this by randomising the hash seed (4.3). Most candidates say "yes, O(1)" and stop.

"Why is Longest Consecutive Sequence O(n) and not O(n^2)?" The amortized argument: the inner loop runs only from run-starts, runs do not overlap, and each number belongs to exactly one run. This is the most common follow-up in the group and it is asked because the code looks quadratic.

"What if the values were bounded — say 1 to n?" Then the hash disappears and an array indexed by value replaces it: no hashing, better cache behaviour, and sometimes O(1) space by reusing the input's sign bits as flags. A bounded small value range turns a hash into an array index, and that realisation is what makes the linear solution to Top K Frequent work.

One thing to volunteer: say explicitly what you chose as the key and why. "I am hashing the sorted letters, because two words are anagrams exactly when that matches." That sentence shows you designed the solution rather than recalled it — and every hard problem in this group is a key-choice problem in disguise.

Recall

  • The pattern: a nested loop whose inner half is a lookup becomes one loop plus a hash map. O(n^2) \to O(n), paid for in space.
  • The skill is choosing the key: the value itself, a derived fingerprint (sorted letters, character counts, difference sequences), or what you still need (target - nums[i]).
  • Check before inserting, always, or an element matches itself.
  • When the sort key is a bounded small integer, do not sort — index into buckets.
  • Two passes in opposite directions replace a nested loop when each answer depends on a prefix and a suffix.
  • Length prefixing beats delimiters when the data may contain any character — the same reason HTTP uses Content-Length.
  • A nested loop is linear when you can prove each element is touched a constant number of times overall.
  • In JavaScript, arrays and objects as Set/Map keys compare by identity; encode to a string or number first.

Next: 4.4.1 Contains Duplicate — the simplest problem in the book, and the one that establishes the check-before-insert discipline every other problem here reuses.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet