Arrays & Hashing

What it is

Arrays store values in order and provide constant-time access by index. Hash sets and hash maps add efficient lookup by value: a set records membership, while a map associates a key with information such as a count or index.

The central technique is to store a compact summary of previously processed data instead of repeatedly searching it. Before choosing a container, decide what a lookup needs to answer:

• Has this value appeared? Use a set.
• Where did it appear? Map the value to an index.
• How many copies exist? Map the value to a count.
• Have two prefixes reached the same state? Map the state to an index or occurrence count.
• Which objects are equivalent? Map a canonical representation to a group.

For example, checking every pair in an array takes quadratic time. Scanning once and looking up each value’s required partner usually takes linear time. The improvement comes from replacing repeated scans with expected constant-time hash-table operations, at the cost of extra memory.

How to recognize it

Arrays and hashing are promising when a statement involves:

• Duplicates, membership, intersections, or values that must be matched.
• Pairs satisfying an equation, especially when one value determines the required other value.
• Frequencies, available quantities, or repeated requests processed in order.
• First or last occurrences of distinct values.
• Contiguous ranges whose counts satisfy a balance condition.
• Grouping objects by shared structure rather than exact representation.
• Consecutive integer values where numerical adjacency matters, not their original positions.

Ask whether the answer depends on order, multiplicity, or both. A set discards both order and multiplicity; a frequency map preserves multiplicity; an index map preserves selected positional information.

Hashing is not automatically preferable to sorting. Sorting may use less auxiliary memory and makes neighboring values easy to compare, but it changes order unless original indices are retained.

The core technique

1. Membership and value-to-index lookup

Use a set when only existence matters. Use a map when finding a value must also reveal its position.

For a pair whose sum must equal a target, a current value x needs a partner equal to target - x. Keep only earlier values in the map:

def find_pair(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        needed = target - x
        if needed in seen:
            return seen[needed], i
        seen[x] = i
    return None

The invariant is that, before processing index i, every stored index is smaller than i. Looking up before inserting prevents using the same element twice.

Choose an update policy deliberately. Overwriting an index retains the latest occurrence. Inserting only when absent retains the earliest. Alternatively, scanning right to left with a set identifies each value’s final occurrence the first time it is encountered; collect those indices and reverse them if increasing index order is required.

Sets also support consecutive-value searches. Start extending a run only at values whose predecessor is absent. Although the algorithm contains a nested loop, each distinct value belongs to only one explored run, so total work is linear on average.

2. Frequency maps and changing inventories

Use counts when repeated values have independent significance. A frequency map can compare multisets, detect duplicates, track available inventory, or summarize a moving range.

For requests processed in order, initialize inventory counts. Accept a request only if its current count is positive, then decrement immediately:

from collections import Counter

def process_requests(items, requests):
    remaining = Counter(items)
    accepted = []
    for value in requests:
        ok = remaining[value] > 0
        accepted.append(ok)
        if ok:
            remaining[value] -= 1
    return accepted

The maintained invariant is that each count equals the unused quantity after all earlier requests. A set would be incorrect because it cannot distinguish one available copy from several.

For contiguous ranges, maintain counts while moving left and right boundaries. Adding the rightmost value increments its count; removing the leftmost decrements it. If a map represents only currently present values, delete entries when their counts reach zero.

Sliding windows require a condition that can be restored by advancing the left boundary, such as having at most a fixed number of distinct values. Frequency tracking alone does not make every range constraint suitable for a sliding window.

3. Hashing prefix states

Use prefix-state hashing when a range property can be expressed as a relationship between its endpoint prefixes.

For equal counts of two symbols, assign one symbol +1 and the other -1. Equal prefix balances imply that the intervening range has net balance zero:

def longest_balanced(symbols):
    earliest = {0: -1}
    balance = best = 0
    for i, symbol in enumerate(symbols):
        balance += 1 if symbol == 'A' else -1
        if balance in earliest:
            best = max(best, i - earliest[balance])
        else:
            earliest[balance] = i
    return best

This assumes every symbol is either A or B. The initial state at index -1 allows a balanced range to begin at index zero.

For several categories, use a tuple of count differences relative to one reference category. With three categories, (count_A - count_C, count_B - count_C) is sufficient. Repeated states mean the intervening range increased all three counts equally.

What the map stores depends on the objective: earliest indices maximize length, latest indices can minimize length, and state frequencies count matching ranges. Related prefix comparisons can track frequency differences between two aligned arrays; a zero difference state means their prefixes contain matching multisets.

4. Canonical keys for grouping

Use a canonical key when different representations should belong to the same group. The key must be identical exactly when the objects satisfy the intended equivalence relation.

Common keys include sorted elements for order-insensitive grouping and count tuples for strings over a fixed alphabet. Adjacent differences encode a numeric sequence’s shape independently of adding the same constant to every element.

If multiple orientations are considered equivalent, compute a representation for each allowed orientation and select a deterministic one, such as the lexicographically smallest tuple. Ensure the transformation is correct: reversing a sequence reverses and negates its adjacent differences.

Store immutable keys, such as tuples, in a map from key to grouped objects. Key construction is part of the algorithm’s cost, not a free operation.

Common mistakes

• Choosing the wrong summary: membership cannot answer multiplicity questions, and a single index cannot preserve every occurrence.
• Violating scan order: inserting before a partner lookup may reuse the current element.
• Overwriting useful history: longest-range calculations need the earliest occurrence of each prefix state.
• Forgetting the empty prefix: omitting it misses valid ranges starting at the first element.
• Leaving zero-count entries: map size then stops representing the number of present values.
• Confusing hash values with keys: store complete keys rather than assuming a manually computed fingerprint is collision-free.
• Mutating keys or ignoring key cost: use immutable representations and account for their construction and comparison.

Complexity

For n elements and d distinct keys, membership scans, pair lookup, and frequency counting typically take O(n) expected time and O(d) space. Prefix-state methods may retain one state per prefix, requiring O(n) space.

Consecutive-run searches also take expected linear time when only run starts trigger exploration. Sliding frequency windows are linear when each element enters and leaves at most once.

Grouping costs depend on the key: sorting a length-m object costs O(m log m), while scanning it to build counts or differences costs O(m). Storing groups also requires space for their contents.

These bounds assume expected constant-time hash operations on bounded-size keys. Long keys add hashing and equality costs; adverse collisions can degrade performance. Arrays indexed by a small, fixed value domain can replace maps for predictable constant-time access.