Arrays & Hashing

Hash Map Lookup

Store what you have seen so each new element can be answered in O(1).

Easy, about 60 minutes to practise.

1Understand

The idea

Walk through the input once and keep what you have seen in a dict or set, so each new element can ask its question ("is my complement here?", "where did I last see this?") in O(1). The trick is deciding what to store as the key and what as the value before you start.

Intuition

Think of the hash map as a notepad you fill while you walk. Each new item asks a question about something you might already have written down. If the answer is there, you are done; if not. Write the current item down for later questions.

The design choice is what to store as the key (the thing you will look up) and what as the value (the fact you need when it hits, often an index). Lookup before insert so an element never pairs with itself unless the problem allows it.

When the question is only membership, a set is enough. When you need "where?" or "how many?", you need a dict. If you catch yourself writing a nested loop that rescans everything already seen, that inner scan is usually a hash map waiting to happen.

What you will be able to do

  • Replace an inner search loop with a hash lookup
  • Decide what key and value to store

When to use it

  • Find a pair or complement (two-sum style)
  • "Have we seen this before?"
  • Nested loops that compare every pair

2See it

Walkthrough

Two Sum, one pass

nums = [2, 7, 11, 15], target = 9, store what you have seen, ask for the complement.

1 / 4

i
2
7
11
15
0123
i → index 0

seen

  • ∅ empty

Start with an empty map. At index 0 the value is 2, so we need complement 9, 2 = 7.

need = target - nums[i] # 7

Live template

Line 3 active

1seen = {}
2for i, x in enumerate(items):
3 if target - x in seen: return (seen[target - x], i)
4 seen[x] = i

Complexity: time O(n), space O(n)

One pass with a hash map is O(n) time and O(n) space. Sorting then two pointers is O(n log n) but loses original indices unless you keep them alongside values. Prefer the map when indices matter; prefer two pointers when the array is already sorted and you only need values.

Read the walkthrough as text

Two Sum (explained). Given nums = [2, 7, 11, 15] and target = 9, return the two indices that add to 9.

Brute force tries every pair: for each i, scan every j > i, O(n²). The insight: standing at value x, you only care whether target, x already appeared. That is a membership question, not a rescan.

  1. Start with an empty map seen from value → index.
  2. At index 0, value 2: need 9, 2 = 7. Not in seen. Store {2: 0} after the lookup.
  3. At index 1, value 7: need 9, 7 = 2. Found at index 0. Return (0, 1).

In code:

  • seen = {}
  • for i, x in enumerate(nums):
  • if target - x in seen:
  • return (seen[target - x], i)
  • seen[x] = i

Why store after the lookup? If the target is 4 and the array has a single 2, looking up first prevents pairing an element with itself.

Same skeleton, different payload: last index for duplicates; running prefix for subarray-sum; frequency for anagrams. The loop shape stays identical. Use the animated example above to watch the map fill.

3Recognise it

Kinds of problems (7)

Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.

  • Complement lookup (two sum)

    Example. Given nums and target, return two indices whose values add to target.

    How. For each value x, ask whether target, x is already in a map of value → index; store x after the lookup.

  • Duplicate detection

    Example. Return true if any value appears twice in the array.

    How. Walk once with a set: if x is already in the set, return true; otherwise add it.

  • First unique / first repeated

    Example. Return the first character that appears only once, or the first that repeats.

    How. Count frequencies in one pass (or store first index), then scan again in order and pick the match.

  • Index of last occurrence

    Example. For each query value, return the last index where it appeared.

    How. Overwrite map[value] = i on every sighting; the map always holds the latest index.

  • Set intersection of two collections

    Example. Return the values that appear in both arrays.

    How. Put one array in a set; scan the other and keep values that hit the set (dedupe with a second set if needed).

  • Sequence starts in a set (longest consecutive)

    Example. Longest run of consecutive integers, unordered input.

    How. Put all values in a set; only start a run from x when x, 1 is missing, then walk x + 1, x + 2, …

  • Validity with sets per row, column or box

    Example. Validate a Sudoku board (no repeats in row, column, or 3×3 box).

    How. Keep a set (or bit mask) per row, column, and box; reject as soon as a digit is already present.

Common mistakes

Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.

  • Store before check

    Why it happens. It feels natural to “remember” the current value as soon as you see it. That breaks the rule that a value must not pair with itself unless the problem allows it.

    How it fails. nums = [2], target = 4. Store seen[2] = 0 first, then ask for complement 2, you “find” index 0 and return a fake pair.

    Fix. Always look up the complement (or membership) before inserting the current value. Insert is the last line of the loop body.

  • Wrong key

    Why it happens. Under time pressure it is easy to swap what you store as key vs value, especially when the answer needs indices.

    How it fails. Storing seen[i] = x (index → value) then asking `if target - x in seen` checks indices, not values, complements never hit.

    Fix. Decide the question first: “have I seen this value?” → value is the key. Need the index later → store value → index.

  • List used for lookups

    Why it happens. A list feels simpler than a set/dict, and `if x in list` looks the same in code.

    How it fails. seen = [] and `if x in seen` on every step makes each check O(n); the whole scan becomes O(n²) and fails large tests.

    Fix. Use a set for membership or a dict when you need a payload (index, count). Membership must stay average O(1).

4Check yourself

Concept check

A short quiz on this lesson before you practise. Optional, and it does not gate coding.

Ready to practise?

Mastery comes from solving. The lesson is optional context.

All lessons