Arrays, strings and hash maps cheat sheet

Spot the first repeated badge at the door

Walk the log once and keep a set of badges already seen. The first badge that is already in the set is the answer. Each check and insert is O(1) on average, so the whole scan is O(n) time and O(n) extra space, against O(n²) for comparing every pair.

def first_repeat(badges: list[int]) -> int:
    seen: set[int] = set()
    for b in badges:
        if b in seen:
            return b
        seen.add(b)
    return -1

Two gift prices that hit the budget exactly

Walk the prices once with a map from price to the first index where it appeared. For each price p at index j, look up budget - p: if it is in the map, that index and j are the answer. One pass, O(n) time and O(n) space, and the tie rule falls out of scanning left to right.

def gift_pair(prices: list[int], budget: int) -> list[int]:
    first_at: dict[int, int] = {}
    for j, p in enumerate(prices):
        need = budget - p
        if need in first_at:
            return [first_at[need], j]
        if p not in first_at:
            first_at[p] = j
    return []

Group tile racks that hold the same letters

Turn each rack into a key that ignores order, then group by that key in a dict. A 26-slot letter count costs O(k) per rack of length k, so the whole job is O(n·k); sorting each rack as the key costs O(n·k log k). The groups and keys take O(n·k) space. Dicts keep insertion order, which gives the required group order for free.

def group_racks(racks: list[str]) -> list[list[str]]:
    groups: dict[tuple[int, ...], list[str]] = {}
    for word in racks:
        counts = [0] * 26
        for ch in word:
            counts[ord(ch) - ord("a")] += 1
        groups.setdefault(tuple(counts), []).append(word)
    return list(groups.values())

Count sales stretches that add up to a target

Keep a running total and a map from each running total to how many times it has appeared. A stretch ending today sums to k exactly when an earlier running total equals today's total minus k, so add that count. One pass, O(n) time and O(n) space. Negative numbers rule out a sliding window, which is why the map is needed.

def count_stretches(sales: list[int], k: int) -> int:
    seen: dict[int, int] = {0: 1}
    total = hits = 0
    for x in sales:
        total += x
        hits += seen.get(total - k, 0)
        seen[total] = seen.get(total, 0) + 1
    return hits

Longest run of consecutive ticket numbers

Put the numbers in a set. A number starts a run only if number - 1 is missing; from each start, count upward while the next number is present. Every number is visited by at most one upward walk, so the work is O(n) on average, versus O(n log n) for sorting first. The set takes O(n) space.

def longest_run(tickets: list[int]) -> int:
    s = set(tickets)
    best = 0
    for x in s:
        if x - 1 in s:
            continue
        end = x
        while end + 1 in s:
            end += 1
        best = max(best, end - x + 1)
    return best

Find the value that fills more than half the list

Use a pair-cancelling vote: keep a candidate and a counter. A matching value adds one, a different value subtracts one, and at zero the next value becomes the candidate. Each cancellation removes one vote for the winner at most together with one other vote, so the winner survives. O(n) time, O(1) space.

def over_half(votes: list[int]) -> int:
    candidate, lead = 0, 0
    for v in votes:
        if lead == 0:
            candidate = v
        lead += 1 if v == candidate else -1
    return candidate

Each shelf's product of all the other shelves

Make two passes. Left to right, write the product of everything before i; right to left, multiply in the product of everything after i, carried in one variable. Each slot ends as before × after. O(n) time and O(1) extra space besides the output, and zeros need no special case because nothing is divided.

def others_product(mult: list[int]) -> list[int]:
    out = [1] * len(mult)
    before = 1
    for i in range(len(mult)):
        out[i] = before
        before *= mult[i]
    after = 1
    for i in range(len(mult) - 1, -1, -1):
        out[i] *= after
        after *= mult[i]
    return out

Shift a playlist k places to the right, in place

Reduce k modulo the length, then reverse the whole list, reverse the first k songs and reverse the rest. Three in-place reversals give the shifted order with O(n) time and O(1) extra space. Slicing (songs[-k:] + songs[:-k]) is shorter but builds a new list.

First order code that appears only once

Count every letter in one pass, then scan again and return the first index whose count is 1. Two linear passes: O(n) time, and O(1) extra space because the alphabet has 26 letters. A nested scan per letter would be O(n²).

def first_single(codes: str) -> int:
    counts: dict[str, int] = {}
    for ch in codes:
        counts[ch] = counts.get(ch, 0) + 1
    for i, ch in enumerate(codes):
        if counts[ch] == 1:
            return i
    return -1

Find the balance point of a seesaw

Compute the grand total once. Then walk left to right keeping the left total: the right total at index i is total - left - w[i]. The first index where they match is the answer. One pass after the sum, O(n) time and O(1) space.

def balance_point(weights: list[int]) -> int:
    total, left = sum(weights), 0
    for i, w in enumerate(weights):
        if left == total - left - w:
            return i
        left += w
    return -1

How a hash map keeps lookups fast on average

A hash map turns a key into a number, maps it to a slot, and checks only the few keys that landed there. The table grows as it fills, so slots stay short and lookups are O(1) on average. Many keys colliding in one slot, from a poor hash or crafted input, degrades a lookup towards O(n).

class SameHash:
    def __init__(self, v: int) -> None:
        self.v = v

    def __hash__(self) -> int:
        return 7

    def __eq__(self, o: object) -> bool:
        return isinstance(o, SameHash) and o.v == self.v


d = {SameHash(i): i for i in range(1000)}
print(len(d), d[SameHash(999)])

Why appending to a list is amortized O(1)

When a list runs out of room, it allocates a bigger block and copies everything, which is O(n). It grows by a fixed proportion, so copies get rarer as the list gets bigger, and the total copying for n appends is O(n). Spread over n appends, that is O(1) each on average: amortized O(1).

What makes a good dictionary key

A key must be hashable: its hash must never change and equal keys must hash equally. Tuples of immutable values qualify; lists can change after insertion, which would strand the entry in the wrong slot, so Python refuses them. Use tuples, frozensets or frozen dataclasses as composite keys.

Count or sort: choosing a frequency tool

Counting with a dict or Counter is O(n) time and O(distinct) space and keeps the original order. Sorting is O(n log n) time but can use O(1) extra space in place and makes equal items neighbours. Prefer counting by default; sort when memory is tight, when you also need order, or when items are not hashable.