leetExpert

Module 6 · Hash Tables

Practice

Practice~1 min

How to practice this module

Hash-table problems reward choosing the key: the pair or group you look up defines the whole solution. Two Sum and Contains Duplicate build complement lookups; First Unique and Group Anagrams turn counts into structure; Longest Consecutive Sequence stretches the key idea to runs. Done when all five show Solved in the hub.

Problems

Hash Tables — work them in order; difficulty ascends.

0/5

solved

  1. 1Two SumEasyComplement lookupWatch for: Store value → index while scanning; return the original indices and never reuse the same element twice
  2. 2Contains Duplicate IIEasyLast-seen index mapWatch for: The window is index distance |i - j| <= k — the map must hold the most recent occurrence
  3. 3First Unique CharacterEasyCount, then scanWatch for: Two passes, first build counts then find the first index with count 1 — a set of seen-once is not enough
  4. 4Group AnagramsMediumSorted-key groupingWatch for: The key is the letter multiset (sorted word or a 26-count), never the original order
  5. 5Longest Consecutive SequenceMediumRun detection from headsWatch for: Only start counting from numbers with no left neighbour; a Set keeps the contains cheap

Cheatsheet

Hash Tables — O(1) average lookup turns nested scans into one pass.

Smell → pattern

  • Need complement / pair for a targetValue → index map
  • Duplicate inside a distance kSliding last-seen
  • First unique / order of appearanceCount then scan
  • Group by signatureKey = sorted / count tuple
  • Long consecutive run without sortSet + expand ends

Patterns

Complement map

Core

Smell: Two-sum family

As you scan, ask ‘have I seen target − x?’ Store value → index. One pass; don’t forget you cannot reuse the same index.

0123

Last-seen index window

Safe

Smell: Duplicates with distance constraint

Map value → latest index. When the gap ≤ k, you have a hit. Overwrite the index as you go.

LRwindow

Count then first pass

Reach

Smell: First unique character / element

Frequency map first, then a stable left-to-right scan for count == 1. Order matters — maps alone lose it.

0123

Canonical key grouping

Core

Smell: Anagrams / isomorphic buckets

Hash a sorted string or a count signature. Every member of a group shares one key — append to that list.

0123

Set + expand consecutive

Careful

Smell: Longest consecutive sequence

Put numbers in a set. Only start a run at n when n−1 is absent — then walk n+1… Length is the walk count.

write region

Complexity targets

  • One-pass complement

    Time
    O(n)
    Space
    O(n)
    Note
    Average hash time

  • Group by signature

    Time
    O(n·k log k)
    Space
    O(n·k)
    Note
    k = key length if sorting

  • Consecutive via set

    Time
    O(n)
    Space
    O(n)
    Note
    Each run starts once

Traps

  • Hashing unhashable structures

    Lists aren’t keys — freeze them (tuple / sorted string / joined counts) before inserting into a map.

  • Average vs worst case

    Interview answers assume average O(1). Pathological collisions exist; still state the average unless asked for worst-case structures.