Arrays and hashing

Arrays and hash-based containers are the two structures most interview problems are built from, and most candidates can quote their complexities without being able to say what those complexities are conditional on. This guide works through the cost model of contiguous storage, the average-versus-worst-case behaviour of hash tables and the key contract they depend on, and the small set of patterns — counting, complement lookup, prefix sums, in-place compaction — that these two structures make linear. The recurring theme is that each pattern buys time with memory, and that saying so precisely is what distinguishes a senior answer from a memorised one.

the contiguous-array cost model

An array is a contiguous block of equally sized slots, which is what makes indexing constant time and makes insertion in the middle linear.

The address of element i is the base address plus i times the element width, so a read needs one multiply-add and one memory access, while inserting at position i has to move every element after it.

An insert at the front of a 1,000,000-element list moves every element; an append moves none.

a = list(range(1_000_000))
a.insert(0, -1)   # ~1,000,000 element moves: O(n)
a.append(1_000)   # amortised O(1)
a[500_000]        # one multiply-add: O(1)

Interview trap. Treating an array as a general-purpose collection whose costs are all similar hides that a mid-sequence insert is O(n) while an append is amortised O(1).

Engineering practice. Choose an array when access is index-driven and mutation happens at the end; move to a linked structure, a deque, or an index-plus-tombstone scheme when the workload inserts in the middle.

amortised append and growth factors

A dynamic array appends in amortised constant time because it grows geometrically rather than by a fixed increment.

When capacity is exhausted the array allocates a larger block — typically 1.5x to 2x — and copies; because the copy cost doubles while the number of appends between copies also doubles, the cost per append averages out to a constant.

CPython over-allocates, so capacity grows in jumps and most appends touch nothing.

import sys
a = []
print(sys.getsizeof(a))              # 56 - the empty list, before any append
for n in range(0, 9):
    a.append(n)
    print(n + 1, sys.getsizeof(a))   # 88, 88, 88, 88, 120, 120, 120, 120, 184

The capacity jumps at 1, 5 and 9 elements: the copies happen there, and the appends between them are free.

Interview trap. Claiming append is O(1) worst case is wrong: the individual append that triggers a resize is O(n), which matters for latency percentiles even when throughput is fine.

Engineering practice. Pre-size the array when the final count is known, and treat tail-latency spikes in append-heavy hot loops as a resize signal rather than a mystery.

the hash-table average versus worst case

Hash-table lookup is O(1) on average and O(n) in the worst case, and the gap between those two is a property of the keys, not of the implementation alone.

Keys are mapped into buckets by a hash function; when many keys collide into one bucket the probe or chain becomes a linear scan, so the bound depends on the hash spreading the actual key distribution.

Keys chosen to share a bucket turn constant-time lookup into a linear scan.

# Every key here hashes to the same bucket in a table of size 8.
adversarial = {i * 8: i for i in range(10_000)}
# Lookup walks the collision chain instead of probing once.

Python randomises string hashing per process by default (PYTHONHASHSEED) precisely so untrusted string keys cannot be made to collide this way.

Interview trap. Quoting O(1) as if it were unconditional ignores adversarial or structured keys that collide deliberately, which is the basis of hash-flooding denial of service.

Engineering practice. Use the platform's randomised or keyed hash for untrusted input, keep load factors bounded, and measure the longest bucket when a lookup-heavy service shows unexplained tail latency.

the hash and equality contract

Two objects that compare equal must have the same hash, and an object used as a key must not change its hash while it is stored.

Lookup first narrows to a bucket by hash and then confirms by equality, so a key whose hash changed after insertion is filed under an address the lookup will never visit.

Mutating a key after insertion files it under an address lookup will never visit.

class Point:
    def __init__(self, x): self.x = x
    def __hash__(self): return hash(self.x)
    def __eq__(self, other): return self.x == other.x

p = Point(1)
seen = {p: "first"}
p.x = 2                 # hash changes while stored
print(p in seen)        # False - the entry is unreachable
print(len(seen))        # 1 - but it is still there

Interview trap. Making a mutable object hashable — or overriding equality without overriding hashing — produces a container that silently loses entries rather than raising an error.

Engineering practice. Key on immutable values or on a stable identifier, and when a custom type is a key, derive both hash and equality from the same fixed set of fields.

load factor and resizing

A hash table's expected probe length is governed by its load factor, the ratio of stored entries to buckets.

As the load factor rises, collisions rise superlinearly, so implementations resize and rehash once a threshold is crossed — an O(n) operation amortised across the insertions that caused it.

A dict of 1,000 small integers costs about 4.6x the packed array of the same values.

import sys
values = list(range(1_000))
print(sys.getsizeof(values))                     # 8,056 bytes
print(sys.getsizeof({v: None for v in values}))  # 36,952 bytes

The dict holds spare buckets by design; CPython resizes when the table is two-thirds full.

Interview trap. Assuming a hash table's memory is proportional to its entries misses that it holds spare buckets by design, often using two to three times the memory of a packed array.

Engineering practice. Reserve capacity up front for known-size builds, and account for the real memory multiplier when a hash-heavy service is sized.

chaining versus open addressing

Chaining stores colliding keys in a per-bucket list, while open addressing stores them in other slots of the same array, and the choice changes cache behaviour more than asymptotics.

Open addressing keeps entries contiguous, which is friendlier to the cache and to prefetching, but degrades sharply at high load factors and needs tombstones to delete correctly; chaining tolerates load better and deletes cleanly at the cost of pointer chasing.

Both are O(1) average, and the cache behaviour differs by several times.

Design	Layout	Delete	Behaviour at load factor 0.9
Chaining	pointer per bucket	remove from list	degrades gently
Open addressing	entries in one array	needs a tombstone	probe length rises sharply

CPython dicts use open addressing, which is why iteration over a dict is cache-friendly and why deletion leaves a DKIX_DUMMY marker rather than a hole.

Interview trap. Reasoning about hash tables purely in big-O terms hides that the two designs can differ several-fold in real throughput at the same asymptotic cost.

Engineering practice. Prefer the platform default unless profiling says otherwise, and when it matters, benchmark with the real key distribution and load factor rather than a synthetic uniform one.

sets as membership structures

A hash set answers membership in expected constant time, which converts many quadratic scan-and-compare loops into linear ones.

Instead of comparing each element with every other, one pass inserts into the set and a second — or the same — pass tests membership, trading O(n) memory for the dropped factor of n in time.

The set turns a 10,000-element quadratic scan into a linear one.

# O(n^2): 50,000,000 comparisons at n = 10,000
any(a[i] == a[j] for i in range(n) for j in range(i + 1, n))

# O(n) time, O(n) memory
len(set(a)) < len(a)

Interview trap. Reaching for a set when order or duplicate counts matter loses information that cannot be recovered afterwards.

Engineering practice. Use a set for presence, a multiset or counter for multiplicity, and an ordered structure when the answer depends on position.

frequency counting

Counting occurrences in one pass with a hash map turns many grouping and anagram problems from sorting-bound to linear.

A single traversal increments a per-key counter; comparisons that would need a sort become equality of two counter maps, and selection of the top k becomes a partial selection over distinct keys rather than over all elements.

Counting is linear; sorting to compare is linearithmic and usually unnecessary.

from collections import Counter
Counter("listen") == Counter("silent")     # True, O(n)
sorted("listen") == sorted("silent")       # also True, O(n log n)

At n = 1,000,000 characters the counter pass is a single scan; the sort is roughly 20 million comparisons.

Interview trap. Sorting to count is not wrong, but claiming it is necessary misses that the O(n log n) is bought only by the ordering, which the question often does not need.

Engineering practice. Count first, then decide whether ordering is genuinely required; when only the top few matter, select over the distinct keys instead of sorting them all.

the complement lookup pattern

Problems asking whether two elements combine to a target become linear when the map is built as the scan proceeds rather than beforehand.

At each element the algorithm asks whether the value it needs has already been seen, then records the current element; each element is therefore both a query and an insertion exactly once.

Building the map as you scan is what keeps an element from pairing with itself.

def two_sum(nums, target):
    seen = {}                        # holds only earlier elements
    for i, v in enumerate(nums):
        if target - v in seen:
            return seen[target - v], i
        seen[v] = i                  # inserted after the query
    return None

two_sum([3, 2, 4], 6)   # (1, 2) - not (0, 0)

Interview trap. Building the full map first and then scanning it reintroduces a bug when an element is allowed to pair with itself, because the index guard is lost.

Engineering practice. Interleave query and insert so the invariant 'the map holds only earlier elements' is structural, and state that invariant aloud rather than patching index checks afterwards.

prefix sums

A prefix-sum array answers any range-sum query in constant time after linear preprocessing.

Storing the cumulative total up to each index means the sum of the half-open range [i, j) is prefix[j] minus prefix[i], which turns a nested query loop into two lookups.

Two lookups replace a loop, and floats lose the guarantee that integers keep.

from itertools import accumulate
a = [3, 1, 4, 1, 5]
p = [0, *accumulate(a)]       # [0, 3, 4, 8, 9, 14]
p[4] - p[1]                   # 6 = sum(a[1:4]), one subtraction

# Floating point does not survive this trick unchanged:
f = [0.1] * 1_000_000
pf = [0.0, *accumulate(f)]
pf[1_000_000] - pf[999_999]   # 0.10000000000582077, not 0.1

Interview trap. Prefix sums over floating-point values accumulate rounding error, so the subtraction can return a materially wrong answer for long arrays of similar magnitudes.

Engineering practice. Use prefix sums freely on integers, and for floats prefer compensated summation or recompute directly when the ranges are short and precision matters.

prefix sums with a hash map

Counting subarrays whose sum equals a target is linear when prefix sums are stored in a hash map keyed by value.

Two indices with prefix sums differing by the target bound a qualifying subarray, so the scan asks how many earlier prefixes equal the current prefix minus the target, and counts them.

Seeding the empty prefix is what makes a subarray starting at index 0 count.

from collections import defaultdict

def count_subarrays(nums, k):
    counts, total, running = defaultdict(int), 0, 0
    counts[0] = 1                      # the empty prefix - drop this and [3], k=3 returns 0
    for v in nums:
        running += v
        total += counts[running - k]
        counts[running] += 1
    return total

count_subarrays([3, 1, 2], 3)   # 2: [3] and [1, 2]

Interview trap. Forgetting to seed the map with a zero prefix drops every subarray that starts at index zero — a defect that passes most hand-written examples.

Engineering practice. Seed the empty prefix explicitly and test the case where the whole array is the answer, which is the case the missing seed always breaks.

in-place array rearrangement

Many array transformations can be done in place with a write pointer that trails the read pointer, using O(1) extra space.

The read pointer visits every element while the write pointer advances only for elements that survive, so the prefix before the write pointer always holds the finished result.

The write pointer trails the read pointer, and the prefix before it is always finished.

def remove_value(a, target):
    write = 0
    for read in range(len(a)):        # read visits every element once
        if a[read] != target:
            a[write] = a[read]
            write += 1
    return write                      # a[:write] is the result

a = [0, 1, 2, 2, 3]
remove_value(a, 2)                    # 3, a[:3] == [0, 1, 3]

Interview trap. Deleting from a list while iterating over it skips elements, because the container shifts under the iterator and the index advances past the shifted-in item.

Engineering practice. Use the two-pointer compaction and return the new logical length, or build a new array when clarity matters more than the allocation.

iterator invalidation

Mutating a container while iterating it is undefined or explicitly forbidden in most standard libraries.

A growing array may reallocate and move its storage, invalidating every outstanding pointer or index; hash containers may rehash and reorder; some libraries detect this and fail fast, and others corrupt silently.

Deleting while iterating skips elements, and the loop finishes without complaint.

a = [1, 2, 2, 3]
for x in a:
    if x == 2:
        a.remove(x)
print(a)                 # [1, 2, 3] - one of the twos survives

d = {"a": 1, "b": 2}
for k in d:
    del d[k]             # RuntimeError: dictionary changed size during iteration

The list version corrupts silently; the dict version fails fast. Do not rely on either behaviour.

Interview trap. Assuming a language that raises a clear error in one container will do the same for all of them is how a rare production corruption gets shipped.

Engineering practice. Collect the changes during the pass and apply them afterwards, or iterate over a snapshot when the container must change during the loop.

grouping by a canonical key

Grouping problems become linear in the number of items once each item is reduced to a canonical key that equal items share.

The key must be a pure function of the equivalence relation — a sorted character tuple, a normalised form, a character count — and it must be hashable, so the grouping is one map insertion per item.

A sorted-character key is injective for anagrams; a character sum is not.

from collections import defaultdict

groups = defaultdict(list)
for word in ["eat", "tea", "tan", "ate"]:
    groups[tuple(sorted(word))].append(word)   # canonical
# {('a','e','t'): ['eat', 'tea', 'ate'], ('a','n','t'): ['tan']}

sum(map(ord, "ad")) == sum(map(ord, "bc"))     # True - a lossy key merges these

Interview trap. Choosing a key that is cheap but not canonical, such as a sum or a length, silently merges groups that are not actually equivalent.

Engineering practice. State the equivalence relation first, then derive a key that is injective with respect to it, and test the pairs that a lossy key would wrongly merge.

hash keys built from sequences

A key derived from a mutable sequence must be converted to an immutable form before it is stored.

Immutable sequence types hash by content, so two equal contents produce one key; mutable ones are either unhashable or hash by identity, which puts equal contents under different keys.

A tuple hashes by content; a join on a separator collides when the data contains it.

key = tuple([1, 2, 3])          # hashable, hashes by content
hash(key) == hash((1, 2, 3))    # True

hash([1, 2, 3])                 # TypeError: unhashable type: 'list'

"-".join(["a", "b-c"]) == "-".join(["a-b", "c"])   # True - two different lists, one key

Interview trap. Serialising the sequence to a string works until a separator appears inside an element, at which point two different sequences collide into the same key.

Engineering practice. Use the language's immutable tuple type, or a serialisation whose escaping is explicit, rather than joining on a character that the data may contain.

insertion-ordered maps

Some hash maps preserve insertion order as a documented guarantee, and others do not, so ordering must be checked against the language contract rather than observed behaviour.

Iteration order in a hash container is otherwise an implementation detail that can change with load factor, with the hash seed, or between releases.

Dict order is guaranteed since Python 3.7; set order is not guaranteed at all.

d = {"b": 1, "a": 2}
list(d)                  # ['b', 'a'] - insertion order, a language guarantee since 3.7

s = {"b", "a"}
list(s)                  # order depends on hash values and table size; do not rely on it

Assert on set(result) when order is irrelevant, and on list(result) only when the contract promises it.

Interview trap. Relying on an observed but undocumented ordering produces a test suite that passes locally and fails after an upgrade or under a different key set.

Engineering practice. When order is part of the answer, use a structure that promises it, and assert on sets rather than on sequences when order is genuinely irrelevant.

sorted structures versus hash structures

A hash structure gives faster point lookups; a balanced or sorted structure gives ordered iteration, range queries, and predecessor and successor queries that a hash structure cannot answer at all.

Ordered structures pay a logarithmic factor per operation to keep a comparison-based invariant, and that invariant is exactly what supports 'the smallest key above x'.

A dict cannot answer 'the smallest key above x' without scanning everything.

import bisect
keys = [10, 20, 30, 40]
bisect.bisect_right(keys, 25)     # 2 -> keys[2] == 30, in O(log n)

d = {10: 'a', 20: 'b', 30: 'c'}
min(k for k in d if k > 25)       # 30, but O(n) every time

Interview trap. Choosing a hash map by default and then reconstructing order by sorting on every query converts a logarithmic operation into a linearithmic one repeated per query.

Engineering practice. Choose from the query mix, not from the insert cost: if any query is a range or an ordered scan, pay the logarithm at write time.

space-for-time as a deliberate trade

The hashing patterns buy time with memory, and that trade has to be sized rather than assumed acceptable.

An index over n items adds O(n) entries plus per-entry overhead — pointers, hashes, spare buckets — which routinely reaches several times the memory of the raw values.

The index is not free: measure it before calling the solution linear.

import sys
a = list(range(1_000_000))
sys.getsizeof(a)                    # 8,000,056 bytes
sys.getsizeof(set(a))               # 33,554,656 bytes - about 4x the array

Reporting the algorithm as O(n) time without saying it is also O(n) space hides the reason it cannot run over a stream.

Interview trap. Reporting an algorithm as O(n) time without stating that it is also O(n) space hides the reason it cannot run over a stream or a dataset larger than memory.

Engineering practice. State both bounds, and when memory is the binding constraint, reach for sorting, streaming, external merge, or a probabilistic structure with a stated error rate.

duplicate detection

Detecting a duplicate is expected linear with a hash set, or linearithmic and constant-space after sorting, and the right choice depends on which resource is scarce.

The set records what has been seen and reports the first repeat immediately; sorting instead brings equal elements adjacent so a single pass compares neighbours.

Set membership is expected O(1) per element; sorting is O(n log n) and constant space.

# Expected O(n) time, O(n) space - reports the first repeat immediately
seen = set()
first_repeat = next((v for v in a if v in seen or seen.add(v)), None)

# O(n log n) time, O(1) extra space if the input may be reordered
a.sort()
any(a[i] == a[i + 1] for i in range(len(a) - 1))

Interview trap. Assuming the set answer is always better ignores that sorting can be done in place and that the set's memory may not be available at the data size in question.

Engineering practice. Default to the set for clarity, switch to sorting when memory is constrained or the input is already ordered, and name the constraint that decided it.

hashing for constant-time deletion

Combining an array with a position map supports insert, delete, and uniform random selection all in expected constant time.

The array holds the elements, the map holds each element's index; deletion swaps the target with the last element, updates that element's index, and pops the tail.

Swap-with-last keeps deletion O(1); shifting to preserve order makes it O(n).

class RandomSet:
    def __init__(self): self.items, self.index = [], {}
    def add(self, v):
        if v in self.index: return
        self.index[v] = len(self.items); self.items.append(v)
    def remove(self, v):
        i = self.index.pop(v)
        last = self.items.pop()
        if i < len(self.items):
            self.items[i] = last          # move the tail into the hole
            self.index[last] = i          # and fix its recorded position

Iteration order is unspecified by construction; document that so callers never depend on it.

Interview trap. Deleting by shifting the array preserves order but reintroduces the O(n) that the structure existed to remove.

Engineering practice. Use the swap-with-last idiom when order does not matter, and document that iteration order is unspecified so callers do not come to depend on it.

matrix traversal as index arithmetic

Two-dimensional problems on a fixed grid are array problems in disguise, and the boundary conditions are where they fail.

A rectangular grid can be addressed as row times width plus column, and neighbour access is offset arithmetic that must be bounds-checked on all four edges before dereferencing.

Bounds-check the candidate before dereferencing it, or a row edge wraps.

MOVES = ((-1, 0), (1, 0), (0, -1), (0, 1))   # one table, so the four checks cannot drift

def neighbours(grid, r, c):
    for dr, dc in MOVES:
        nr, nc = r + dr, c + dc
        if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]):   # both dimensions, before use
            yield grid[nr][nc]

Checking only the row lets column -1 read the last cell of the previous row: legal Python, wrong answer.

Interview trap. Checking bounds after computing the neighbour index — or checking only one dimension — wraps around the row edge and reads a legal but wrong cell.

Engineering practice. Guard each candidate index before use, keep the offsets in one table so the checks cannot drift apart, and test corners explicitly.

encoding state in the array itself

When the value range is bounded and disjoint from the index range, an array can encode marks in place and drop the auxiliary structure entirely.

Negating a value, adding an offset larger than the maximum, or writing a sentinel records a visit at position i without a separate seen-set, and the original value stays recoverable.

Negation marks a visit with no extra memory, but only when the domain excludes the sentinel.

def find_duplicates(nums):          # values are 1..n, so index n-1 is always in range
    out = []
    for v in nums:
        i = abs(v) - 1
        if nums[i] < 0: out.append(abs(v))
        else: nums[i] = -nums[i]    # mark seen, in place
    for i in range(len(nums)): nums[i] = abs(nums[i])   # restore before returning
    return out

The trick fails the moment the input can contain 0 or a negative value.

Interview trap. The trick fails silently when the input can contain the sentinel or when the caller expects the array to come back unmodified.

Engineering practice. Use it only when the value domain is documented, restore the array before returning, and prefer the extra memory when the input contract is uncertain.

cache locality and the constant factor

Two structures with the same asymptotic cost can differ severalfold in wall time because of memory locality, and the gap widens as the data outgrows the cache.

A contiguous array is read in cache-line-sized blocks with hardware prefetching, while a pointer-based structure incurs a dependent load — and a possible cache miss — per element.

Same asymptotics, measurably apart in wall time.

import timeit
setup = "a = list(range(1_000_000)); s = set(a); d = dict.fromkeys(a)"
timeit.timeit("sum(a)", setup, number=10)   # ~0.04s - contiguous, prefetched
timeit.timeit("sum(s)", setup, number=10)   # ~0.05s - scattered buckets

Both are O(n). The difference is memory layout, and it is the difference a benchmark at realistic size actually measures.

Interview trap. Concluding that a linked structure is faster because its insertion is O(1) ignores that the traversal needed to reach the insertion point dominates the measurement.

Engineering practice. Benchmark at the real data size, and prefer contiguous layouts unless the mutation pattern genuinely demands otherwise.

stating complexity precisely

A complexity claim is only meaningful once n is defined and the case — average, amortised, or worst — is named.

For array-and-hash solutions n is usually the element count, but the answer can also depend on the number of distinct keys, the alphabet size, or the length of each key, and hashing a long key is not free.

Hashing a length-k key is not free, so the bound is O(nk), not O(n).

# n keys, each k characters. The loop is n iterations; each hash reads k bytes.
seen = set()
for key in keys:          # n
    seen.add(key)         # hashing this key is O(k)
# total: O(nk) time, O(nk) space for the stored keys

At n = 1,000,000 and k = 64 that is 64 million byte reads, not 1 million operations.

Interview trap. Saying 'O(n) because we loop once' while hashing a string of length k on each iteration understates the true O(nk).

Engineering practice. Name every parameter in the bound, state whether it is average or worst case, and say what the space bound is in the same breath.

choosing between the array and hash patterns

The pattern follows from the query the problem actually asks, not from the shape of the input.

Membership and counting go to a hash structure; order, rank, and range go to a sorted structure; positional and windowed questions stay on the array with pointers; and prefix aggregates go to a precomputed table.

The query decides the structure, and each one refuses a different question.

Query	Structure	Cost
Is x present?	set	O(1) expected
How many x?	Counter	O(1) expected
Smallest key above x?	sorted list + bisect	O(log n)
Sum of a[i:j]?	prefix-sum array	O(1) after O(n)
Element at position i?	list	O(1)

A set cannot answer the third row at all, and a sorted list answers the first row a logarithm slower. Pick from the query, not from the input's shape.

Interview trap. Pattern-matching on surface features — 'it is an array, so two pointers' — produces a solution that is correct on the example and wrong on the constraint the interviewer added.

Engineering practice. Restate the query in one sentence, choose the structure that answers that query directly, and say out loud what you gave up by choosing it.