Arrays and Hashing

Start with the missing information

Presence, counts and indices

A set forgets multiplicity. For [2,2,5], presence is {2,5}; counts are {2:2,5:1}. Comparing these sets cannot establish that two multisets are equal. Frequency maps can compare multisets, rank frequent values, group by frequency or maintain window requirements.

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

Before checking nums[i], seen contains exactly nums[:i]'s values. A repeated membership scan through a list can do 1+2+…+(n−1) comparisons. A set exchanges additional state for average constant-time lookup under the hashing model.

def frequency_counts(nums):
    from collections import Counter
    return Counter(nums)

If position matters, store an index. Decide whether it is the first or latest occurrence: unconditional overwrite keeps the latest; insertion only when absent keeps the first. That decision can change distance and tie-breaking results. Counts need updates, not only presence checks.

Turn a search into a lookup

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

For [3] and target 6, checking after insertion would incorrectly match index 0 with itself. For [3,3], the second 3 may correctly use the first. No sorted-order assumption is needed.

The function returns one pair, not every pair. Listing all pairs can itself require quadratic output. A value-to-single-index map also deliberately forgets other occurrences; use a richer representation if the question needs them.

A key must preserve the grouping rule

An anagram grouping key must preserve character multiplicities but forget their order. Sorted characters give a tuple key with O(m log m) sorting work for a length-m word. For a fixed lowercase a–z alphabet, a 26-count tuple takes O(m+26) work and constant-sized state per key.

Those assumptions matter. A 26-slot implementation must reject or handle other characters rather than silently index them. For general Unicode, define normalization, case policy and whether the problem counts code points or user-perceived characters. Do not normalize unless the requested equivalence allows it.

def group_anagrams(words):
    groups = {}
    for word in words:
        counts = [0] * 26
        for char in word:
            if not 'a' <= char <= 'z':
                raise ValueError('expected lowercase ASCII')
            counts[ord(char) - ord('a')] += 1
        groups.setdefault(tuple(counts), []).append(word)
    return list(groups.values())

The character sum is not a valid canonical key: “ad” and “bc” have equal sums but are not anagrams. This is a semantic collision in the representation. A normal hash collision is different: a correct map still compares keys for equality.

Python keys must be hashable. A tuple of counts works; a mutable list does not. Keep equality-relevant key state stable. A hash digest alone is not a proof that two original objects are equal unless the problem accepts its collision risk.

Reuse what lies on either side

First write the left product into each output slot, then walk backward and multiply by the right product. This avoids division, so zeros need no special divide-by-zero branch. One zero leaves only its own slot potentially nonzero; two zeros make all slots zero.

def product_except_self(nums):
    out = [1] * len(nums)
    p = 1
    for i, value in enumerate(nums):
        out[i] = p
        p *= value
    s = 1
    for i in range(len(nums) - 1, -1, -1):
        out[i] *= s
        s *= nums[i]
    return out

The prefix is updated after writing; the suffix is updated after multiplying. Reversing either order accidentally includes the item meant to be excluded. The result array is O(n), while the two scalar accumulators are O(1) auxiliary state excluding output.

For additive ranges, use exclusive prefix sums $P_0=0,\quad P_{i+1}=P_i+a_i$. The sum of [l,r) is $P_r-P_l,\quad 0\le l\le r\le n$. Addition supports subtraction; a minimum cannot generally be removed from a prefix this way. Choose an operation with the necessary algebra.

Range queries after the data changes

A prefix snapshot answers static sums cheaply. Changing one value changes every later prefix. Choose the structure from the update policy and aggregate, not from the number of queries alone.

Fenwick: remove one binary block at a time

The public array is zero-indexed. The internal tree uses indices 1 through n; slot 0 is unused. For positive i, lowbit(i) is i & −i. Slot i stores the sum of the zero-based interval [i−lowbit(i),i). A prefix query subtracts lowbit from its endpoint. A point delta instead adds lowbit to visit every block containing that point.

For [2,7), subtract prefix(2)=3 from prefix(7)=28: the sum is 25. Adding 10 to zero-based index 4 visits internal slots 5,6,8. The new prefix(7) is 38 and the same range sum is 35.

def fenwick_add(tree, index, delta):
    if not 0 <= index < len(tree)-1: raise IndexError(index)
    index += 1
    while index < len(tree):
        tree[index] += delta
        index += index & -index

def fenwick_prefix(tree, end):
    if not 0 <= end < len(tree): raise IndexError(end)
    total = 0
    while end:
        total += tree[end]
        end -= end & -end
    return total

Allocate tree=[0]*(n+1), then add each input value. This simple build costs O(n log n); a linear build also exists. prefix(end) sums [0,end), including the empty prefix. A range uses prefix(r)−prefix(l), with integer bounds 0≤l≤r≤n. Updates mutate tree, not an original input array. Assignment needs delta=new−old, so retain the old value. These functions expect integer indices and integer additive data. General range minima cannot be obtained by subtracting two prefix minima. Fenwick binary-block derivation ↗

Segment tree: merge a disjoint interval cover

Each leaf stores one value; each parent merges its left and right summaries. Pad to a power-of-two leaf count with the operation’s identity, then build parents bottom-up. A query takes a whole node when its interval is inside the request, skips disjoint nodes, and descends only at partial overlaps. A point assignment recomputes its ancestors.

Unlike prefix subtraction, a segment query can combine minima without an inverse. The merge must be associative; it need not be commutative. Preserve left-to-right order for concatenation or matrix products. The empty sum is 0; the empty minimum needs an identity such as positive infinity. Build and storage are O(n), while point assignment and range query are O(log n) for bounded-cost merges. Large summaries add their own cost. Range updates require a separate lazy-tag design; they are not implemented by the Fenwick point-delta code. Segment construction, query and update contracts ↗

Scan each consecutive run once

The earlier set example remembers the processed prefix. A different task needs the complete set: finding consecutive integer values regardless of input order. Duplicates do not extend a run.

For [100,4,200,1,3,2,2], the distinct runs are 1–4, 100 and 200. Starting a forward scan at every value repeatedly visits the same suffix. Instead, start at x only when x−1 is absent. Every finite run has exactly one such start.

def longest_run_length(nums):
    values = set(nums)
    best = 0
    for start in values:
        if start - 1 in values:
            continue
        end = start
        while end in values:
            end += 1
        best = max(best, end - start)
    return best

Inside the while loop, every integer from start up to end, excluding end, has been found. On exit, end is the first missing successor. Their difference is the run length.

The loops are nested, but their work is not multiplied. Each distinct value belongs to one run, and only that run’s start launches its scan. With u distinct values, the outer loop makes u predecessor checks. All inner loops together make u successful membership checks and one failed check per run.

Building the set reads n input items. Under average constant-time hashing and unit-cost integer operations, total time is O(n), with O(u) extra space. Iterating over the original array instead can rescan a run once for every duplicate start. Empty input returns 0; a singleton returns 1. The function does not change its input.

Count work, including keys and outputs

Hashing and comparing long keys can cost more than O(1). Arbitrary-precision arithmetic also changes the unit-cost assumption for large products. Memory, collision behavior and input constraints determine whether the usual shorthand is appropriate.

Finding frequent values is counting plus selection, not automatically a full sort. Heaps, sorting or frequency buckets are choices after the frequency map exists. Ordered pair reasoning belongs in Pointers and Sliding Windows →.

Choose a representation and state its invariant

Before writing a loop, name the key, its stored value and the eligible range. Then specify lookup/update order. Test empty input, one item, duplicates, zero, negative numbers and a case with no answer.

Do not change map size while iterating over its dynamic entries; iterate over a snapshot or defer structural edits. For counts, delete zero-count entries when map size represents the number of distinct values. For grouping, test values that would collide under an overly weak key.

A useful practice progression is presence → multiset comparison → complement lookup → grouping → frequency selection → exclusive prefix/suffix state → run starts. The pattern, its proof and its conditions are the reference; individual exercise writeups are not new atlas topics.

Related patterns and sources

Python mapping and key semantics ↗ · Counter frequency semantics ↗ · CPython built-in operation costs ↗

The CPython cost table assumes constant-time key hashing and equality. Other implementations or custom keys can have different costs; average lookup cost is not a worst-case guarantee.

Use Ordering and Selection after counting when only the most frequent values are needed. Use Windows and Two Pointers for range-specific state.