Arrays and Hashing

Arrays and hash maps are the foundation of most coding interviews. A large share of "easy" and "medium" problems reduce to one idea: trade a little memory for a lot of speed by remembering what you have already seen. This chapter teaches the toolkit: hash sets for membership, hash maps for counting and grouping, prefix sums for range queries, and the habit of asking "what would I like to look up in constant time?"

1. When this pattern applies

Reach for hashing when you notice any of these:

• You keep searching for something in a list inside a loop.
• The problem asks about duplicates, counts, frequencies, pairs or complements.
• You need to group items by some property.
• You need to answer many range queries on a fixed array, or count subarrays with a property.
• The brute force is $O(n^2)$ because of a nested scan, and the inner scan is looking for a specific value.

The question to ask: "For each element, what exactly am I looking for, and can I look it up directly?"

2. The toolkit in Python

from collections import Counter, defaultdict

seen = set()                      # membership in O(1) average
counts = Counter("banana")        # frequency map
groups = defaultdict(list)        # key -> list, no KeyError on first use

assert 3 not in seen
assert counts["a"] == 3 and counts["z"] == 0     # a missing key in a Counter is 0
groups["x"].append(1)
assert groups["x"] == [1]

Facts to keep in mind:

• Keys must be hashable: numbers, strings and tuples of hashables work, lists do not. To use a list as a key, convert it to a tuple.
• Lookups, inserts and deletes are $O(1)$ on average.
• A set is a hash map without values.
• Iteration order of a dictionary is insertion order (Python 3.7 and later), which is sometimes useful, though you should not rely on it for correctness in other languages.

3. Pattern A: membership and duplicates

Contains duplicate. Return whether any value appears twice.

Brute force compares every pair, $O(n^2)$. Sorting then comparing neighbours is $O(n\log n)$. A set gives $O(n)$: if a value is already in the set, there is a duplicate.

def contains_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

assert contains_duplicate([1, 2, 3, 1]) is True
assert contains_duplicate([1, 2, 3, 4]) is False

Time $O(n)$, space $O(n)$. A common follow-up: "what if memory is tight?" Then sort in place and scan neighbours, trading time for space.

4. Pattern B: complements (two sum)

Covered in the first chapter: for each number, look up target - x in a map of values seen so far. The same idea solves many variants: pairs with a given difference, pairs whose sum is divisible by $k$ (store remainders), and "find two numbers in a sorted array" (where two pointers beat the map on space, see the next chapter).

5. Pattern C: counting and grouping

Group anagrams. Words that are anagrams of each other share the same sorted letters. Use the sorted word as a key.

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))          # canonical form of an anagram class
        groups[key].append(w)
    return list(groups.values())

result = group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]

Time $O(n\cdot k\log k)$ for $n$ words of length $k$ (sorting each). A faster key is a tuple of 26 letter counts, giving $O(n\cdot k)$:

def group_anagrams_counts(words):
    groups = defaultdict(list)
    for w in words:
        count = [0] * 26
        for ch in w:
            count[ord(ch) - ord("a")] += 1
        groups[tuple(count)].append(w)    # a tuple is hashable, a list is not
    return list(groups.values())

result = group_anagrams_counts(["eat", "tea", "tan", "ate", "nat", "bat"])
assert sorted(sorted(g) for g in result) == [["ate", "eat", "tea"], ["bat"], ["nat", "tan"]]

The lesson is the idea of a canonical key: transform each item into a form that is identical for items that should be grouped.

Top K frequent elements. Count with a Counter. To pick the $k$ most frequent, you could sort the counts ($O(n\log n)$), use a heap ($O(n\log k)$), or use bucket sort by frequency, which is $O(n)$ because a frequency cannot exceed $n$:

from collections import Counter

def top_k_frequent(nums, k):
    count = Counter(nums)
    buckets = [[] for _ in range(len(nums) + 1)]   # index = frequency
    for value, freq in count.items():
        buckets[freq].append(value)
    result = []
    for freq in range(len(buckets) - 1, 0, -1):    # highest frequency first
        for value in buckets[freq]:
            result.append(value)
            if len(result) == k:
                return result
    return result

assert sorted(top_k_frequent([1, 1, 1, 2, 2, 3], 2)) == [1, 2]
assert top_k_frequent([1], 1) == [1]

Bucket sort is a good idea whenever the values you sort by lie in a small known range.

6. Pattern D: prefix sums

When you need the sum of many ranges of a fixed array, precompute prefix sums: prefix[i] is the sum of the first i elements. Then the sum of nums[l..r] is prefix[r + 1] - prefix[l].

class RangeSum:
    def __init__(self, nums):
        self.prefix = [0]
        for x in nums:
            self.prefix.append(self.prefix[-1] + x)

    def sum(self, left, right):                   # inclusive
        return self.prefix[right + 1] - self.prefix[left]

r = RangeSum([3, 4, -2, 5, 1])
assert r.sum(1, 3) == 7 and r.sum(0, 4) == 11 and r.sum(2, 2) == -2

Building is $O(n)$, each query is $O(1)$. The same idea works for 2D grids (prefix sums over rectangles) and for counting (prefix counts of a character).

Product of array except self. A variation: build the product of everything to the left of each index, then the product of everything to the right, and multiply. No division is needed, so zeros are handled safely.

def product_except_self(nums):
    n = len(nums)
    out = [1] * n
    left = 1
    for i in range(n):                 # out[i] = product of nums[0..i-1]
        out[i] = left
        left *= nums[i]
    right = 1
    for i in range(n - 1, -1, -1):     # multiply by product of nums[i+1..]
        out[i] *= right
        right *= nums[i]
    return out

assert product_except_self([1, 2, 3, 4]) == [24, 12, 8, 6]
assert product_except_self([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]

Time $O(n)$, extra space $O(1)$ beyond the output.

7. Pattern E: prefix sum plus hash map (subarray sums)

Subarray sum equals $k$. Count the contiguous subarrays whose sum is exactly $k$. The array may contain negatives, so sliding window does not work.

Idea: let running be the sum of the prefix so far. A subarray ending here has sum $k$ exactly when some earlier prefix had sum running - k. So keep a map from prefix sum to how many times it occurred.

from collections import defaultdict

def subarray_sum_equals_k(nums, k):
    seen = defaultdict(int)
    seen[0] = 1                         # the empty prefix
    running = count = 0
    for x in nums:
        running += x
        count += seen[running - k]      # earlier prefixes that complete a subarray here
        seen[running] += 1
    return count

assert subarray_sum_equals_k([1, 2, 3, -1], 3) == 2
assert subarray_sum_equals_k([1, 1, 1], 2) == 2
assert subarray_sum_equals_k([1, -1, 0], 0) == 3

Time $O(n)$, space $O(n)$. The base case seen[0] = 1 is the part people forget: it represents the empty prefix and lets a subarray that starts at index 0 be counted.

This pattern, prefix state plus a map, generalises. To find the longest subarray with equal numbers of 0s and 1s, treat 0 as $-1$ and find the longest span between equal prefix sums. To find subarrays divisible by $k$, store prefix sums modulo $k$.

8. Pattern F: sets for sequences

Longest consecutive sequence. Given unsorted numbers, find the length of the longest run of consecutive integers, in $O(n)$.

Sorting gives $O(n\log n)$. With a set, start a run only at numbers that have no predecessor in the set, then walk up. Each number is visited at most twice, once as a possible start and once while extending a run.

def longest_consecutive(nums):
    values = set(nums)
    best = 0
    for x in values:
        if x - 1 not in values:           # x starts a run
            length = 1
            while x + length in values:
                length += 1
            best = max(best, length)
    return best

assert longest_consecutive([100, 4, 200, 1, 3, 2]) == 4
assert longest_consecutive([]) == 0
assert longest_consecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9

The while inside the for looks quadratic but is not: the inner loop only runs from run starts, so each element is walked over once in total. This is the same amortised argument from the complexity chapter.

9. Arrays: in-place and index tricks

Several array problems use the array itself as the data structure.

Move zeroes to the end, preserving order. Keep a write pointer for the next non-zero slot.

def move_zeroes(nums):
    write = 0
    for read in range(len(nums)):
        if nums[read] != 0:
            nums[write], nums[read] = nums[read], nums[write]
            write += 1
    return nums

assert move_zeroes([0, 1, 0, 3, 12]) == [1, 3, 12, 0, 0]

Find the missing number in 0..n using the sum formula (or XOR). The sum of 0..n is $n(n+1)/2$:

def missing_number(nums):
    n = len(nums)
    return n * (n + 1) // 2 - sum(nums)

assert missing_number([3, 0, 1]) == 2
assert missing_number([0, 1]) == 2

Rotate an array by $k$ using three reversals, in place and $O(n)$:

def rotate(nums, k):
    n = len(nums)
    k %= n
    nums.reverse()
    nums[:k] = reversed(nums[:k])
    nums[k:] = reversed(nums[k:])
    return nums

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

Using the input as a hash. When values lie in 1..n, you can mark presence by negating nums[value - 1], giving an $O(1)$ space duplicate or missing-number finder. Mention this as an optimisation, and note that it modifies the input.

10. How to choose among the techniques

11. Common mistakes

• Mutating a collection while iterating over it. Build a new one, or iterate over a copy.
• Forgetting the base case seen[0] = 1 in prefix-sum counting.
• Checking and storing in the wrong order in two sum, so an element pairs with itself.
• Using a list as a dictionary key. Convert to a tuple.
• Assuming sorted order of a dictionary or set for correctness.
• Using sliding window on arrays with negative numbers when the problem needs prefix sums and a map.
• Off-by-one in prefix sums, since the prefix array has $n+1$ entries.
• Integer division and negative remainders. In Python, -1 % 5 is 4, which is convenient, and differs from C++ and Java.

12. Practice set

Work these in order, and say the brute force, the bottleneck and the optimisation out loud for each.

1. Valid anagram.
2. Two sum II (sorted input), then the hash version.
3. Contains duplicate II (within distance $k$).
4. Encode and decode strings (a canonical-key idea).
5. Subarray sums divisible by $k$.
6. Continuous subarray sum (multiple of $k$).
7. Contiguous array (equal 0s and 1s).
8. First missing positive (using the array as a hash).
9. Majority element (hash map, then Boyer-Moore voting).
10. Range sum query 2D (prefix sums on a grid).