Pattern: kill the inner loop

The N+1 of interviews

A Pune billing job compared every invoice with every other invoice to find a matching settlement. Two loops. Fine at 2,000 rows. At 2 lakh rows the batch window died.

I have seen the same shape in code reviews for ten years. The inner loop is a search. A search you could have replaced with a lookup.

In plain words: a hash map (dictionary) or hash set remembers what you already walked past, so you do not walk the list again.

When you finish this lesson you should be able to read n and know whether nested loops will time out. You should hear "find a pair," "have I seen this," or "count this" and reach for the right map. You should say the six-step interview script out loud before you type.

The problems after this (Contains Duplicate, Two Sum, anagrams) are homework on this one idea. Do not skip this page to "just see the code." The code is the last twenty percent.

Tradeoff: you pay RAM to buy time. That is the whole family.

Why Should You Care?

Days 3 and 4 of the 90-day plan are this family. Day 3 is Contains Duplicate and a stock scan. Day 4 is Two Sum, Valid Anagram, and Group Anagrams. If this page is mushy, every later hash problem feels new.

At work this is the same idea as a Redis cache. You look it up, or you compute it and remember it. You just never named it on an array. The Pune billing batch was not a clever algorithm problem. It was an inner loop that should have been a lookup.

In interviews, product companies grade process. If you only recite the map solution, they ask what else you considered, and you freeze. They want brute force said out loud, then killed. The map is step 4, not step 1.

🟢 The Simple Version (start here)

Think of an attendance register or a quick checklist in memory: When a new item arrives, you do not scan the entire notebook from top to bottom. You check that exact entry in O(1) time:

• If the item is already marked, you know immediately it is a duplicate.
• If not, you record it and continue.

Looking up an entry in a hash set or hash map takes O(1) average time. Comparing against every previous element with a nested loop takes O(n) per item, which grows to O(n²) for the entire array.

Hash set: "have I seen this value?" Only membership.

Hash map: "I have seen this value, and I stored something with it" (index, count, a list of words).

The inner loop in brute force is almost always "search for the partner." The set or map is that search with the walking removed.

Brute force                         After the map
for each A:                         for each A:
  for each B:          kill this →    look up partner in the map
    if A and B match                    if found, done
                                      else store A

The one question I want you to ask on every array problem:

Can I replace a nested search with a lookup?

If yes, this is the pattern.

Recognition signals

If the array is already sorted and they want indices of a pair, do not reach for a map first. That is Two Sum II. Different family. Two pointers. We teach that after these problems.

If the phrase fits a map, pause anyway. Some prompts look like lookup and are not.

Wrong family: when a hash is the wrong first tool

Sorted Two Sum II looks like Two Sum. The prompt still says "two numbers that add to target." The difference is the array is already sorted, and they often want O(1) extra memory. A map still finds the pair. They then ask why you spent O(n) RAM when two indices walking inward would have done it. The sort is the hint. Use it.

Walk [2, 7, 11, 15], target 9, both ways so you feel it. The map stores 2 → 0, then at 7 it looks up 2 and returns. Fine, and extra RAM. Opposite ends: 2 + 15 = 17 (too big, drop 15), 2 + 11 = 13 (too big, drop 11), 2 + 7 = 9. Same pair, two integers of extra memory. That is the family they wanted.

A contiguous slice looks like "have I seen this." Longest substring without repeating characters on abca is the trap. A set of the whole string sees a twice and wants to say "duplicate exists." That is Contains Duplicate. The actual question is the longest contiguous slice with unique letters. abc is legal (length 3). After the second a arrives, you drop the first a and keep bca (still 3). The set is a running fact for the current slice, and you throw the left end away when the slice breaks. That is a sliding window. Membership of the whole array is the wrong question.

UPI makes the same split at work. "Have we already processed this txnId?" is a set (or a unique index). "How many callbacks in the last 60 seconds?" is a window. If you dump every callback id into a set and call it a rate limit, you answered a different question.

The reverse mistake is also common, so I will name it. Unsorted [3, 2, 4], target 6, they want original indices. Sit i on 3 and j on 4. Sum 7, too big, so a Two Sum II loop moves j and never looks at 2 + 4. The proof that you can throw an end away needs sorted order. You do not have it. Look up target - x in a map. That is this week's tool.

Do not sort "to make two pointers legal" if they asked for original indices. Sort shuffles the positions unless you stored them first. Then you have built a slower, fussier map.

How big-O actually talks

In plain words: Big-O is the shape of the work as n grows. It is not milliseconds on your laptop.

Library with n books:

Interview time limits are roughly 1 to 2 seconds. Nested loops on n = 10⁵ are about 10¹⁰ visits. Dead. Nested loops on n = 10³ might pass and still get a "can you do better?"

Three counting rules

1. Drop constants. O(3n) is O(n).
2. Drop the smaller term. O(n² + n) is O(n²).
3. Quote the worst case unless they ask average.

Space is extra memory, not the input array. A set of n keys is O(n) extra. Two integers is O(1) extra.

Backend picture, because you already live here:

You precompute so you do not recompute. That is the pattern.

Constraint cheat table (say this in the room)

Read 1 <= n <= ... before you pick a technique.

If the prompt says n = 10⁵ and you start two nested loops, you have already told them you did not read constraints.

n lookups is O(n), not O(1). Each lookup is O(1) average. The loop still walks n items.

The 6-step interview script

Product companies grade this more than clever syntax. Use it on every problem in this path.

1. Restate and clarify (2 min). Own words. Ask: duplicates? negatives? empty? return indices or values? sorted?
2. Read n. Say the target complexity out loud.
3. Brute force first (2 min). Describe the dumb correct idea and its Big-O. You do not have to type it. They need to hear it.
4. Optimize. Ask "can I kill the inner loop?" Apply the map or the set.
5. Code and narrate. Names that say what they hold (need, seen, not x2).
6. Dry-run and complexity. Walk one sample. State time and extra memory.

If you skip step 3, a mid-level interviewer thinks you memorised NeetCode. If you skip step 1, you return values when they wanted indices.

Here is the same script on Two Sum, the one they will actually ask.

Restate. Two different indices whose values add to target. Classic prompt: exactly one pair.

Clarify. Duplicates allowed ([3,3] target 6). Negatives allowed. Return indices. Not sorted.

n. Often 10⁴. O(n²) is borderline. O(n) is the bar.

Brute. For i, for j > i, if sum matches, return. O(n²) time, O(1) extra.

Optimize. The inner loop searches for target - nums[i]. Store earlier values in a map. Look up, then store.

Time O(n), extra O(n). You bought the linear scan with a map of up to n keys.

Dry-run: Two Sum on [2, 11, 15, 7], target 9

I moved 7 to the end on purpose. The usual sample [2, 7, 11, 15] hits on the second index and hides the loop. Walk this one on paper. Look up before you insert.

You never nested a second loop. At i = 3 the partner was already sitting in the map from i = 0.

Now the trap. [3, 3], target 6. If you insert then look up, the first 3 lands in the map, the lookup finds the same index, and you return [0, 0]. The prompt said two different indices. Look up need first. Miss. Store. Next 3 looks up 3, finds index 0, returns [0, 1].

The usual sample [2, 7, 11, 15], target 9, is the same story in two rows. i = 0 stores 2 → 0. i = 1 needs 2, hits, returns [0, 1]. You still walk it in the room so they see you can.

Dry-run: Contains Duplicate on [1, 2, 3, 1]

Same spike, no partner, only membership.

If the last 1 had been a 4, the set would hold four keys and you would return false after the loop. That is the whole set shape.

Notice what you did not do. You did not sort. Sorting also finds a duplicate (equal neighbours), but it is O(n log n) and it shuffles indices if a later problem needs them. For "does any duplicate exist," the set is the honest first tool at n = 10⁵.

Three map shapes you will reuse

Complement map (Two Sum family): key is the value you saw, value is the index. Look up target - x before you insert x, so you never pair an element with itself.

Membership set (Contains Duplicate): only the keys. If insert fails (already there), you found a duplicate.

Frequency or group map: count letters, or bucket words by a signature. Valid Anagram and Group Anagrams.

I will not dump four languages here. Each problem does that after you have thought.

🔴 Architect's Corner

At India scale you do not load 10 crore ids into a process set to detect duplicates. That is a unique index, or a Bloom filter if you can live with false positives.

The interview still wants the in-memory set. Say both sentences: "For this n, a HashSet. In a KYC table with crores of PANs, I would not do this in the app."

Hash collisions exist. In the room, treat lookup as O(1) average unless they are fishing for that.

A map is a tool for n that fits in memory. The Pune job at 2 lakh invoices fits. A day of UPI txnIds across India does not. Do not let the interview answer become the production design by accident.

Common Mistakes

The belief is that starting with the optimal map looks senior. They then ask brute force and you blank. Process is the grade. Say the nested loop, then kill it.

The belief is that "hash is O(1), so the whole algorithm is O(1)." n lookups is O(n). Each glance is cheap. You still glance n times.

The belief is that sorting first is always safer. Sort shuffles indices. If they asked for original positions, you now have to store them, and you have paid O(n log n) for a problem a map solves in O(n).

The belief is that insert-then-lookup is the same as lookup-then-insert. On [3, 3] target 6 you match an index with itself. Look up the partner first.

The belief is that a map is the answer to every pair problem. Sorted Two Sum II wants two pointers. A contiguous budget wants a window. The map still appears inside a window as a running count. The family is not "hash the whole array."

The belief is that a set of everything you have ever seen answers "longest unique slice." That is Contains Duplicate thinking on a window prompt. Drop the left end, or you are solving the wrong question.

🧠 Key Takeaways

The inner loop is a search. A map is that search without the walk. You read n before you pick a technique. You say brute force out loud, then you kill it. You look up, then you store. You are buying time with RAM, and that is the tradeoff you say in the room. If they already sorted the array, or if they asked for a contiguous slice, you give that RAM back and pick the other family.

Think About It

1. n = 10⁵, you need a pair that sums to target. Why is "I will sort, then two pointers" a different problem if they want original indices?
2. A webhook handler must reject a duplicate paymentId it saw in the last 24 hours. Is the interview HashSet still the production answer?
3. Why does "exactly one solution" change what you return when the loop ends?

Pause here. Next lesson is Contains Duplicate. Open it only after you can say the one question without looking.