Array & Hash Table

When reading 7 in [2,7,11] with target 9, ask whether 2 appeared earlier. Start with that lookup, then separate counting, prefix information and position marking.

Two principles hold for the whole article:

1. At every moment, be able to say which part of the input the table holds. Usually it is "everything before the current position", that is [0, i). Whether you look up before you store, and what the initial value is, both follow from that sentence.
2. The key decides what counts as "the same". Two elements belong to the same class exactly when their keys are equal. Once the key is right, the rest of the code is just counting or appending.

Each step below adds exactly one idea to the previous one:

When to Use This Pattern

The brute force is two nested loops: the outer loop reaches i, and the inner loop scans everything before i to see whether the thing you want is there. That is O(n²). If you put the elements you have passed into a hash table, that inner scan becomes one O(1) lookup, so the whole thing is O(n), at the cost of O(n) extra space.

Take Two Sum with nums = [2, 7, 11, 15] and target = 26, and count the comparisons made at each element:

The brute force makes 0 + 1 + 2 + … + (n−1) comparisons; the hash version makes 1 per row. The swap works because the inner loop is only asking "has this value appeared before?", and a hash table answers that directly.

Recognition Checklist

• The inner loop of the brute force only checks whether some value appeared earlier
• You need the number of times each element or each feature appears
• Elements must be grouped by a shared feature (letter counts, relative gaps, which row / column / box)
• The question asks for contiguous subarrays with sum k, and the array may have negatives
• The solution must be in place with O(1) extra space, and values map one-to-one onto indices
• You are asked to design a structure that supports several operations, each in O(1)

Before You Code

Answer these three before writing code.

1. What is the brute force's inner loop looking for? Write it as one sentence: "I need to know whether X appeared / how many times / where." X is the key; "how many" or "where" is the value.
2. Which part of the input does the table hold right now? Usually [0, i). That sentence decides the order: if you are looking for something earlier, you must look up first and only then put yourself in. It also decides the initial value: if "nothing seen yet" counts as a case of its own, put it in the table up front.
3. Can you skip the table? If values are in 1..n, the index can be the key; a matrix can use its first row and column as a notebook; a sorted array can use two pointers instead. This is the path to take when the interviewer asks for O(1) space.

Count nonempty contiguous subarrays summing to k; negatives are allowed. The input below has two matches, [1,2] and [3], so return 2 rather than a maximum length.

Try it on LC 560 Subarray Sum Equals K with nums = [1, 2, 3], k = 3:

• What the inner loop looks for: the brute force tries every (l, r) and checks sum(nums[l..r]) == k. With prefix sums pre this becomes pre[r+1] - pre[l] == k. Fix r, and the inner loop is asking "how many earlier prefix sums equal pre - k?" So the key is a prefix sum and the value is how many times it has appeared.
• What the table holds: every prefix sum before the current position, including the empty prefix with sum 0. So the table starts as {0: 1}, and each step looks up pre - k first and then stores the current pre.
• Can you skip the table: no. With negatives the prefix sums are not monotonic, so neither indices nor two pointers can replace it.

Step 3 turns this paragraph into code.

Two Sum (LeetCode 1)

Given an unsorted integer array and target, return zero-based indices of two different positions; exactly one pair is guaranteed. One position cannot be reused, but equal values at different positions can be paired. The trace computes that index pair.

Input: nums = [3, 2, 4], target = 6. Expected: [1, 2].

seen maps each value already passed to its index.

1. Walk it by hand

2. Read the rule off the table

• Every row computes need = target - num and looks it up in seen.
• If need is there, the answer is its stored index plus the current i.
• If not, store num: i after the lookup, so an element never pairs with itself.

3. Turn each row into code

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        need = target - num
        if need in seen:
            return [seen[need], i]
        seen[num] = i
    return []

Core Templates

All five steps use the same routine: answer the three questions, then check the code against the two principles. What does the table hold? Does the key separate "the same" correctly?

Step 1: Look up as you go, then store

Problem: in an unsorted array, find two numbers that add up to target and return their indices (LC 1 Two Sum).

Given an unsorted integer array nums and an integer target, return the indices of two different positions whose values add up to target. Indices start at 0. Exactly one answer is guaranteed.

For example, [3, 3] with target = 6 → [0, 1]: the two 3s sit at different positions, so they can pair; one position cannot be used twice.

The asserts below also test a single number and an empty array, where the function returns []. That is extra behavior of this helper; LC 1 never gives such inputs.

The three questions:

• What the inner loop looks for: at num, whether target - num appeared earlier, and at which index. The key is the value; the value is the index.
• What the table holds: seen holds only nums[0..i-1].
• Can you skip the table: the array is unsorted and we need original indices; sorting would scramble them, so we need the table.

The first principle gives the code directly: the table may only contain elements already passed, so look up need first and only then put yourself in. That way an element never pairs with itself.

def two_sum(nums, target):
    seen = {}                       # value -> index, only nums[0..i-1]
    for i, num in enumerate(nums):  # enumerate yields (index i, value num) each round
        need = target - num
        if need in seen:            # look up first: num itself is not in the table yet
            return [seen[need], i]
        seen[num] = i               # then store
    return []


assert two_sum([3, 2, 4], 6) == [1, 2]
assert two_sum([3, 3], 6) == [0, 1]
assert two_sum([3], 6) == []
assert two_sum([], 1) == []

nums = [3, 2, 4], target = 6:

Each number is looked up once and stored once, and dict lookups and stores are O(1) on average, so the total is O(n) time and O(n) extra space.

If you store before looking up. With nums = [3] and target = 6: at i = 0 you store 3: 0, then look up need = 3, find yourself, and return [0, 0]. That breaks the first principle: at lookup time the table contains an element that should not be there yet.

One more step: how many pairs add up to target

Practice here (original problem) ↗

Given an integer array nums and an integer target, return how many index pairs (i, j) have i < j and nums[i] + nums[j] == target. Pairs with equal values at different positions count separately.

For example, [3, 3, 3] with target = 6 → 3: (0, 1), (0, 2) and (1, 2) are each a pair.

Think first: Last time the table stored an index and you returned on the first hit. Now you must count every pair. When you reach num, what do you want the table to tell you about need? Do you still look up before storing?

def count_pairs(nums, target):
    cnt = {}                        # value -> count within nums[0..i-1]
    pairs = 0
    for num in nums:
        pairs += cnt.get(target - num, 0)   # look up first: one pair per earlier need
        cnt[num] = cnt.get(num, 0) + 1      # then store
    return pairs


assert count_pairs([1, 5, 7, -1, 5], 6) == 3
assert count_pairs([3, 3, 3], 6) == 3
assert count_pairs([1, 2], 6) == 0
assert count_pairs([], 0) == 0

Variant: the table holds everything (LC 128 Longest Consecutive Sequence)

Given an unsorted integer array nums, return the length of the longest run of consecutive integers: the largest L such that x, x+1, …, x+L−1 are all in the array. An empty array returns 0.

For example, [100, 4, 200, 1, 3, 2, 2] → 4: the values 1, 2, 3 and 4 are all present. They need not be adjacent or in order in the array, and the second 2 does not make the run longer.

The required time is O(n), so sorting first is out.

Think first: So far the table held only "elements already passed". Here you only care whether a value is present, not where it is or what came first. Does the table still need to hold only the elements passed? Counting upward from every number counts the same run many times; how do you count each run only once?

def longest_consecutive(nums):
    s = set(nums)                   # the table holds the whole array
    best = 0
    for x in s:
        if x - 1 in s:              # not a start; skip so each run is counted once
            continue
        y = x
        while y + 1 in s:
            y += 1
        best = max(best, y - x + 1)  # the run is x..y, both ends included
    return best


assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
assert longest_consecutive([100, 4, 200, 1, 3, 2, 2]) == 4   # the example above
assert longest_consecutive([7, 7, 7]) == 1
assert longest_consecutive([]) == 0
assert longest_consecutive([0, -1, 1]) == 3

Variant: has this state appeared before (LC 202 Happy Number)

Given a positive integer n, replace it with the sum of the squares of its digits, and keep repeating. Return True if it eventually becomes 1, otherwise False.

For example, 19 → 1² + 9² = 82 → 68 → 100 → 1, so return True. 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 is back at 4, a cycle without 1, so return False.

Think first: There is no array here. What are the "elements already passed"? If the number never becomes 1, what does the sequence do? How do you notice that and stop?

def is_happy(n):
    seen = set()                    # numbers already seen
    while n != 1:
        if n in seen:               # seen before: we are in a cycle
            return False
        seen.add(n)
        n = sum(int(d) ** 2 for d in str(n))
    return True


assert is_happy(19) is True
assert is_happy(2) is False
assert is_happy(1) is True
assert is_happy(7) is True

Step 1 recap

• What it solves: when the inner loop searches for "something seen earlier", a table turns that O(n) backward search into an average O(1) lookup.
• The key line: if need in seen comes before seen[num] = i: look up, then store.
• What the variants change: need an index, store indices (LC 1); need a pair count, store counts (count_pairs); only care whether values exist, put the whole array in a set and count from run starts (LC 128); states are generated step by step, store the states seen (LC 202).
• Easiest mistake: storing before looking up, so an element pairs with itself. [3] with target = 6 returns [0, 0].

In Step 1 the key is always the element itself. In many problems the elements that should count as the same look different, like "eat" and "tea". Then you have to build the key yourself, which is Step 2.

Step 2: Counting and grouping: choosing the key

Problem: group a list of strings into anagrams (LC 49 Group Anagrams).

Given a list of strings strs, each made of lowercase English letters, return them in groups. Two strings are anagrams when every letter appears the same number of times in both; only the order may differ.

For example, ["eat", "tea", "tan", "ate"] → [["eat", "tea", "ate"], ["tan"]]. The order of groups and the order within a group do not matter.

What must match is how many times each letter appears, not just which letters appear: "aab" and "abb" both use only a and b, but they are not anagrams. Keep duplicate strings, and put the empty string "" into a group too.

The three questions:

• What the inner loop looks for: at a word, where is "the group of its anagrams"? The value is the list of words in that group.
• What the table holds: every word in [0, i), grouped by key. Order of lookup and store does not matter here, since every word joins its own group.
• Can you skip the table: no, the number of groups is not known in advance.

All the difficulty sits in the second principle: which key makes anagrams equal and non-anagrams different? Anagrams are defined as "every letter appears the same number of times", so use the 26 letter counts directly as the key. Three things in the code need explaining:

• cnt = [0] * 26: 26 slots, cnt[0] counts a and cnt[25] counts z. ord(c) - ord("a") turns a letter into 0..25: ord returns a character's code, a through z have consecutive codes, so subtracting the code of a gives "which letter". For "eat", cnt is 1 at indices 0 (a), 4 (e) and 19 (t) and 0 elsewhere; "tea" produces the same cnt, so they land in the same group.
• tuple(cnt): a dict key must be hashable. A list is mutable; if it could be a key and its contents later changed, the dict could no longer find it under its old hash. So Python refuses lists as keys, and groups[cnt] raises TypeError: unhashable type: 'list'. A tuple is immutable, so it can be a key, and two tuples with equal contents are equal and hash the same.
• defaultdict(list): works like a normal dict, except that reading a missing key first calls list() to create an empty list, stores it, and returns it. So you can .append(w) even the first time a key shows up. A plain dict raises KeyError here; you would write groups.setdefault(key, []).append(w) instead.

"".join(sorted(w)) also works as a key: sorted("tea") gives ['a', 'e', 't'], joined back into "aet". But sorting costs O(k log k) per word, while counting is O(k), where k is the word length.

from collections import defaultdict


def group_anagrams(strs):
    groups = defaultdict(list)          # a missing key starts as an empty list
    for w in strs:
        cnt = [0] * 26
        for c in w:
            cnt[ord(c) - ord("a")] += 1
        groups[tuple(cnt)].append(w)    # a list is unhashable; use a tuple
    return list(groups.values())


def norm(groups):
    return sorted(sorted(g) for g in groups)


assert norm(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]
assert norm(group_anagrams(["eat", "tea", "tan", "ate"])) == [["ate", "eat", "tea"], ["tan"]]   # the example above
assert norm(group_anagrams(["aab", "abb"])) == [["aab"], ["abb"]]
assert norm(group_anagrams(["", ""])) == [["", ""]]
assert group_anagrams([]) == []

With n words of length k, the total time is O(n·k). norm sorts each group and then the list of groups, only so the tests do not depend on group order or order within a group.

One more step: group shifted strings (LC 249)

Given a list of strings, each nonempty and lowercase, put strings that can be shifted into one another into the same group, and return the groups in any order.

One shift replaces every letter of a string with the next letter of the alphabet, with z wrapping around to a. "abc" shifted once is "bcd", and "az" shifted once is "ba". Any number of shifts keeps a string in the same group. Unlike anagrams, letters stay in their positions.

For example, ["az", "ba", "a", "z"] → [["az", "ba"], ["a", "z"]].

Think first: "abc" and "bcd" differ at every position, and their letter counts differ too. What do they have in common? When z wraps around to a, does that common thing break, and how would you fix it?

def group_shifted(strs):
    groups = defaultdict(list)
    for w in strs:
        # i starts at 1: each w[i] minus the letter before it, len(w) - 1 gaps
        key = tuple((ord(w[i]) - ord(w[i - 1])) % 26 for i in range(1, len(w)))
        groups[key].append(w)           # neighbor gaps do not change under a shift
    return list(groups.values())


assert norm(group_shifted(["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"])) == [["a", "z"], ["abc", "bcd", "xyz"], ["acef"], ["az", "ba"]]
assert norm(group_shifted(["az", "ba", "a", "z"])) == [["a", "z"], ["az", "ba"]]   # the example above
assert group_shifted([]) == []
assert norm(group_shifted(["ab", "ba"])) == [["ab"], ["ba"]]

One more step: put "where" into the key (LC 36 Valid Sudoku)

Given a 9×9 board board whose cells are the characters "1" through "9" or "." for an empty cell, decide whether the filled cells follow the rules: no digit repeats within a row, a column, or a 3×3 box. Return True if so, otherwise False.

Only check the current board. You do not have to solve it or prove it can be completed. Empty cells are ignored.

For example, two "5" cells in row 0 → False.

Think first: You have to check 9 rows, 9 columns and 9 boxes for repeats. 27 sets would work; can a single set do it? What must go into the key so that "row 0 has a 5" and "column 0 has a 5" are never treated as the same fact? Which box does cell (r, c) belong to?

def is_valid_sudoku(board):
    seen = set()
    for r in range(9):
        for c in range(9):
            v = board[r][c]
            if v == ".":
                continue
            keys = [("r", r, v), ("c", c, v), ("b", r // 3, c // 3, v)]
            if any(k in seen for k in keys):    # v already in this row, column or box
                return False
            seen.update(keys)                   # add all three keys to the set
    return True


empty = [["."] * 9 for _ in range(9)]
assert is_valid_sudoku(empty) is True
row_dup = [r[:] for r in empty]     # r[:] copies each row, so every test edits its own board
row_dup[0][0] = row_dup[0][8] = "5"
assert is_valid_sudoku(row_dup) is False
box_dup = [r[:] for r in empty]
box_dup[0][0] = box_dup[2][2] = "5"
assert is_valid_sudoku(box_dup) is False
ok = [r[:] for r in empty]
ok[0][0] = ok[4][4] = "5"
assert is_valid_sudoku(ok) is True

One more step, in reverse: the count becomes the index (LC 347 Top K Frequent).

Given an integer array nums and an integer k, return the k distinct values that appear most often, in any order. The answer is guaranteed unique: the k-th and (k+1)-th place never tie.

For example, [1, 1, 1, 2, 2, 3] with k = 2 → [1, 2]: 1 appears 3 times, 2 appears twice and 3 once, so take the top two.

Follow-up: do better than O(n log n) time.

Think first: Counting each value is Step 2's counting. Then you need the k values with the highest counts. Without sorting, what is the largest count a value can have? Could you use the count as an index and drop each value into the matching slot?

from collections import Counter


def top_k_frequent(nums, k):
    freq = Counter(nums)                            # value -> count
    buckets = [[] for _ in range(len(nums) + 1)]   # index is the count, at most n
    for x, f in freq.items():
        buckets[f].append(x)
    res = []
    for f in range(len(nums), 0, -1):              # counts from n down to 1
        for x in buckets[f]:
            res.append(x)
            if len(res) == k:
                return res
    return res


assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([5], 1) == [5]
assert sorted(top_k_frequent([4, 4, 6, 6, 7], 2)) == [4, 6]

Variant: counting without a table (LC 169 Majority Element)

Given a nonempty array nums of length n, return the value that appears more than n/2 times. Such a value is guaranteed to exist.

For example, [2, 2, 1] → 2: n = 3, and 2 appears twice, more than 1.5.

Follow-up: O(n) time and O(1) extra space. A Counter needs O(n) extra space, so it does not meet the follow-up.

Think first: Without a table you cannot store each value's count. Suppose you repeatedly pair up two different numbers and cross both out. Who is left at the end? Why can the value that fills more than half the array never be crossed out completely?

def majority_element(nums):
    cand, votes = None, 0
    for x in nums:
        if votes == 0:
            cand = x                # votes ran out; switch candidates
        votes += 1 if x == cand else -1
    return cand


assert majority_element([2, 2, 1, 1, 1, 2, 2]) == 2
assert majority_element([2, 2, 1]) == 2   # the example above
assert majority_element([3, 2, 3]) == 3
assert majority_element([7]) == 7
assert majority_element([1, 2, 3]) == 3   # no majority, yet a candidate is still returned

The keys side by side:

Step 2 recap

• What it solves: elements that look different but should count as the same get a key you build, so they compare equal; then you count or group.
• The key line: groups[tuple(cnt)].append(w). Keys must be hashable, so the list becomes a tuple.
• What the variants change: only how the key is computed. Anagrams use the 26 letter counts (LC 49), shifts use neighbor gaps mod 26 (LC 249), Sudoku writes row, column and box tags into the key (LC 36); LC 347 flips the count into an index; LC 169 drops the table altogether and cancels instead of counting.
• Easiest mistake: a key that separates too little or too much. Without the "r" and "c" tags, a 5 in row 0 collides with a 5 in column 0; without the mod, "az" and "ba" end up in different groups.

Steps 1 and 2 look up single elements. When the question is about a contiguous range, you first have to turn the range into a single value you can look up. That is Step 3.

Step 3: Prefix sums + hashing: ranges become Step 1

Problem : count the contiguous subarrays whose sum is k ( LC 560 ); the array may contain negatives. (Pro lesson)

One more step: the longest subarray with sum k (LC 325)

Given an integer array (negatives allowed) and k, return the length of the longest contiguous subarray whose sum is k, or 0 if there is none… (Pro lesson)

Variant: prefix information does not have to go into a hash table (LC 238 Product of Array Except Self)

Given an integer array nums (length at least 2, zeros and negatives allowed), return an array answer of the same length where answer[i] is t… (Pro lesson)

Variant: 2D prefix sums (LC 304)

Build NumMatrix once from a matrix that never changes, then answer repeated calls to sum_region(row1, col1, row2, col2) (called sumRegion on… (Pro lesson)

Variant: difference arrays, prefix sums run backwards (LC 3355 Zero Array Transformation I)

Given a nonnegative array nums and a list of queries, each an inclusive range [l, r] . (Pro lesson)

Step 3 recap

What it solves : "a range sums to k" becomes "two prefix sums differ by k", so a range problem turns back into Step 1's look-up-as-you-go. (Pro lesson)

Step 4: The index is the information

Problem : find the smallest positive integer missing from an unsorted array, in O(n) time and O(1) extra space ( LC 41 First Missing Positiv… (Pro lesson)

Variant: the first row and column as a notebook (LC 73 Set Matrix Zeroes)

Given a nonempty m×n matrix, if a cell is originally 0, set its entire row and column to 0. Modify the matrix in place; (Pro lesson)

Variant: coordinate maps (LC 48 Rotate Image, LC 54 Spiral Matrix)

LC 48 Rotate Image: given an n×n matrix, rotate it 90° clockwise in place . For example, [[1, 2], [3, 4]] → [[3, 1], [4, 2]] . (Pro lesson)

One more step: the index is a place value (LC 43 Multiply Strings)

Given two nonnegative integers num1 and num2 written as strings, return their product, also as a string. (Pro lesson)

Step 4 recap

What it solves : when only O(1) extra space is allowed, write the record onto the input itself, so an index or position means "this value ap… (Pro lesson)

Step 5: Design problems: fix one contradiction at a time

Problem : design a set where insert , remove and getRandom all run in average O(1) ( LC 380 ). (Pro lesson)

One more step: build a hash table yourself (LC 706 / 705)

LC 706 Design HashMap: without the language's built-in hash table, implement a map from integer keys to integer values with three operations… (Pro lesson)

One more step: encode a list of strings (LC 271 Encode and Decode Strings)

Design two functions: encode(strs) turns a list of strings into one string, and decode(data) turns it back into the original list. (Pro lesson)

Step 5 recap

What it solves : the problem gives operations and complexity targets, and you assemble the structure. (Pro lesson)

The five steps together

Step What the table holds Key Value The line that matters Step 1 elements already passed, [0, i) the element itself index / count look up ne… (Pro lesson)

One Problem, Many Disguises

Disguise (how the problem is phrased) Underlying problem Step LC 202 Happy Number: does the digit process loop has this state appeared befor… (Pro lesson)

Common Pitfalls

Storing before looking up in Two Sum. With nums = [3] and target = 6 the element pairs with itself and you return [0, 0] . (Pro lesson)

Say It in the Interview

Start with the brute force and why it is slow, then say what the map stores, and bring up the {0: 1} edge case yourself: The brute force che… (Pro lesson)