Arrays & Hashing cheatsheet

#️⃣ Arrays & Hashing

Spend O(n) memory on a set or dict so every "have I seen it?" costs O(1).

Recognize the pattern

"Any duplicates?" / "seen before?" → a seen set, check then add
Unsorted array + find a pair with a sum/difference → dict of value → index, look up target - x
"Anagrams", "same letters", "same pattern" → group by a canonical key (sorted string or count tuple)
"Most frequent", "top k", "appears more than" → Counter, then bucket sort by count
Answer at i uses everything except nums[i], no division → prefix and suffix passes
O(n) required where sorting would help → a set for membership (e.g. start-of-run checks)
Uniqueness per row/column/box or per slope → a set of tuple keys

Seen set

Python template

def has_duplicate(nums: list[int]) -> bool:
    seen: set[int] = set()
    for x in nums:
        if x in seen:       # check first...
            return True
        seen.add(x)         # ...then add
    return False

Counting

Counter reads missing keys as 0; two Counters are equal when all counts match (anagram check).

Python template

from collections import Counter

counts = Counter(nums)          # O(n)
counts[x] += 1                  # manual update
top = counts.most_common(k)     # [(val, cnt), ...]

# plain dict version
d: dict[int, int] = {}
for x in nums:
    d[x] = d.get(x, 0) + 1

Group by canonical key

Python template

from collections import defaultdict

def group(words: list[str]) -> list[list[str]]:
    groups: dict[tuple, list[str]] = defaultdict(list)
    for w in words:
        key = [0] * 26
        for ch in w:
            key[ord(ch) - 97] += 1
        groups[tuple(key)].append(w)  # tuple!
    return list(groups.values())

Complement lookup (Two Sum)

Python template

def pair(nums: list[int], target: int) -> list[int]:
    index_of: dict[int, int] = {}
    for i, x in enumerate(nums):
        if target - x in index_of:
            return [index_of[target - x], i]
        index_of[x] = i
    return []

Bucket sort by frequency

Python template

from collections import Counter

def top_k(nums: list[int], k: int) -> list[int]:
    buckets = [[] for _ in range(len(nums) + 1)]
    for v, c in Counter(nums).items():
        buckets[c].append(v)
    out: list[int] = []
    for c in range(len(nums), 0, -1):
        out.extend(buckets[c])
        if len(out) >= k:
            return out[:k]
    return out

Prefix / suffix passes

For "everything except i": one pass left to right, one right to left. Swap * for + or max as needed.

Python template

def except_self(nums: list[int]) -> list[int]:
    n = len(nums)
    out = [1] * n
    for i in range(1, n):            # before i
        out[i] = out[i - 1] * nums[i - 1]
    right = 1
    for i in range(n - 1, -1, -1):   # after i
        out[i] *= right
        right *= nums[i]
    return out

Operation costs

Operation	Time	Space
set/dict add, lookup, delete	O(1) avg	O(1)
x in list	O(n)	—
build set / Counter of n items	O(n)	O(n)
sorted-string key for a word of length k	O(k log k)	O(k)
count-tuple key for a word of length k	O(k)	O(26)
bucket sort by frequency	O(n)	O(n)

Watch for

Lists (and sets, dicts) can't be keys: convert with tuple(...) or frozenset(...).
Two Sum: insert AFTER checking, or you'll pair an element with itself.
dict[key] raises KeyError on a missing key; use .get(key, 0), Counter or defaultdict.
Reading a defaultdict creates the key: use key in d to test membership.
Float keys (like slopes) round badly: use a gcd-reduced (dy, dx) tuple with a fixed sign.
Sets and dict keys have no useful order for 'first' questions: scan the original list instead.