Patterns — A Coding Cheatsheet

PREP CHEATSHEET

i. Complexity — quick reference

O(1)

Constant. Same work, any input size. dict lookup, array index, ptr vars.

O(log n)

Halving each step. binary search, bisect.

O(n)

Walk each item once. one pass, Counter, Kadane's.

O(n log n)

Sort then sweep. sorted(), merge intervals.

O(n²)

Every pair. nested loops, brute force.

O(n + k)

Linear + buckets. counting sort, bucket sort.

O(2ⁿ)

Exponential — every subset. naive backtracking.

→ Full visual primer with curves, mental models & real numbers on page 3.

ii. The Verbal Opener — six beats, every problem

Restate"What I'm hearing is: given X, return Y. Did I get that right?"
ClarifySize? Empty? Duplicates? No-answer return? Time vs space?
ExamplesWalk 1–2 inputs by hand, out loud, before any code.
ApproachBrute force first, name its O. Then optimal, name its O.
CodeNarrate each line. State the invariant out loud.
TestTrace fresh input. Sweep the edge-case checklist.

iii. The Patterns — When you see X, reach for Y

find a pair summing to target — unsorted input

Hash Map of
Complements

O(n) O(n) space dict

For each x, ask the notebook: have I seen target − x? If yes, return the pair. If no, write x in. One pass.

find a pair summing to target — sorted input

Two
Pointers

O(n) O(1) space indices

L at start, R at end. Sum too small → L++. Sum too big → R−−. Sorted means moving L only raises sum, R only lowers. Never backtrack.

longest / shortest substring with property

Sliding
Window

O(n) O(k) space dict + L,R

R expands the window. When the invariant breaks (dup char, sum > k, >k distinct), L advances until it's repaired. Each index visited ≤ 2× → linear.

does anything repeat? has X been seen?

Set
Existence

O(n) O(n) space set

A bouncer at a door with a guest list. Walk the input — if the name is already on the list, that's the duplicate. Otherwise write it and move on.

how many of each? frequency map

Counter /
defaultdict

O(n) O(k) space Counter

One walk, increment. counts[c] += 1 with defaultdict(int). Counter(seq) is the same in one call. .most_common(k) gives top-K for free.

top K elements · K-th largest · streaming median

Min-Heap
of Size K

O(n log k) O(k) space heapq

Hold the K best you've seen. heappush a new one, heappop the smallest if size > K. Python only ships min-heap — negate values for max-heap.

sorted array — find element / boundary fast

Binary
Search

O(log n) O(1) space bisect

Peek the middle. Eliminate the half that can't contain the answer. Repeat. Decide low <= high vs low < high intentionally — bug-magnet otherwise.

next greater / next smaller / span on the right

Monotonic
Stack

O(n) O(n) space list

Stack stays monotonic (decreasing, say). New item comes in: pop everything smaller — each pop pairs that popped element with the new one. Each item pushed + popped at most once → linear.

PG · 01 / 03

PATTERNS — PRINT LANDSCAPE · CHEATSHEET

PREP CHEATSHEET

linked list — middle, cycle, n-th from end

Slow + Fast
Pointers

O(n) O(1) space pointers

Fast moves two, slow moves one. When fast hits the end, slow's at the middle. If there's a cycle, they meet inside it. Constant space — no extra set.

group items by some derived key

Hash Map
of Lists

O(n·k) O(n) space defaultdict(list)

Compute a stable key (sorted letters, frequency tuple, etc.). groups[key].append(item). defaultdict(list) auto-creates the bucket on first sight — skips the if key not in groups dance.

merge / insert overlapping intervals

Intervals
Merge

O(n log n) O(1)+ space list

Sort by start. Walk. If current.start ≤ last.end → extend last.end. Else append new. The sort lets the sweep be one pass — adjacency is no longer hidden.

tree / graph — depth, shape, levels, paths

DFS or
BFS

O(n) O(h) / O(w) recursion / queue

DFS: recurse. Stack = call stack. Use for depth, path-existence, tree shape. BFS: deque, .popleft(). Use for shortest distance, level-by-level. Always carry a visited set for graphs.

iv. Idiom Shapes — burn these in your fingers

FREQUENCY · DICT

from collections import defaultdict

counts = defaultdict(int)
for c in s:
    counts[c] += 1
return counts

TWO POINTERS · SORTED

L, R = 0, len(arr) - 1
while L < R:
    s = arr[L] + arr[R]
    if s == target:
        return [L+1, R+1]
    elif s < target: L += 1
    else:           R -= 1

SLIDING WINDOW · LONGEST

seen, L, best = {}, 0, 0
for R, c in enumerate(s):
    if c in seen and seen[c] >= L:
        L = seen[c] + 1
    seen[c] = R
    best = max(best, R - L + 1)

BINARY SEARCH · EXACT MATCH

L, R = 0, len(arr) - 1
while L <= R:
    mid = (L + R) // 2
    if arr[mid] == target: return mid
    elif arr[mid] < target: L = mid + 1
    else:                  R = mid - 1
return -1

STACK · VALID PARENS

pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for c in s:
    if c in pairs:
        if not stack or stack.pop() != pairs[c]:
            return False
    else: stack.append(c)
return not stack

HEAP · TOP K

import heapq
heap = []
for x in nums:
    heapq.heappush(heap, x)
    if len(heap) > k:
        heapq.heappop(heap)
return heap   # top K (any order)

BFS · LEVEL ORDER

from collections import deque
queue = deque([start])
visited = {start}
while queue:
    node = queue.popleft()
    for neighbor in graph[node]:
        if neighbor not in visited:
            visited.add(neighbor)
            queue.append(neighbor)

DFS · RECURSION

def dfs(node):
    if not node: return           # base case
    # process node here
    dfs(node.left)
    dfs(node.right)
    return result

v. Quick Index — additional reaches

Signal	Pattern	T · S	Note
"in-place reverse / swap"	Two Pointers	O(n)O(1)	`a, b = b, a` idiom; meet in middle.
"max contiguous sum"	Kadane's	O(n)O(1)	Extend running sum; reset if it dips below zero.
"rotated sorted array"	Binary Search v.	O(log n)O(1)	One half is always sorted — recurse into it.
"design X with O(1) ops"	Hash + Aux	O(1)O(n)	LRU = dict + doubly-linked list. Min Stack = stack + min stack.
"any permutation = anagram"	Hash Map	O(n)O(k)	`Counter(a) == Counter(b)`.
"longest consec sequence"	Hash Set	O(n)O(n)	Only start counting at `x` if `x-1` not in set.
"3Sum / 4Sum"	Two Pointers	O(n²)O(1)	Fix one, two-pointer the rest. Skip duplicates carefully.
"shortest path / fewest steps"	BFS	O(V+E)O(V)	Queue. First time you reach a node = optimum (unweighted).
"first / last occurrence (sorted + duplicates)"	Biased Binary Search	O(log n)O(1)	On match: record + keep narrowing (left or right) instead of returning. Two passes.
"stack with O(1) min query"	Stack	O(1)O(n)	Parallel stack tracks `min(new, current_min)` at each push.
"LRU cache / O(1) get + put"	Hash Map + Doubly-Linked List	O(1)O(cap)	Dict gives lookup. DLL tracks recency — head=most recent, tail=evictable.
"max area / two lines container"	Two Pointers	O(n)O(1)	Always move the shorter side inward — moving the taller can never win.
"reverse linked list"	Linked List Reversal	O(n)O(1)	Walk through. Save next, point `curr.next` backward to prev, advance.
"all paths / word search / N-queens"	Backtracking (DFS + undo)	exp.O(depth)	Try a choice → recurse → undo on the way out. Mark / recurse / unmark.
"product of array except self"	Prefix + Suffix Passes	O(n)O(1)*	Two passes. Left pass = product of everything before i. Right pass = after i. Multiply.
"longest palindromic substring"	Expand Around Center	O(n²)O(1)	Try each char (and each gap) as center. Expand outward while chars match.
"min steps / fewest coins / DP"	Bottom-Up DP	O(n·k)O(n)	`dp[i]` = answer for size i, built from smaller subproblems.
"longest substring with K replacements"	Sliding Window + Max-Count	O(n)O(k)	Window valid iff `size − max_count ≤ K`. Track max count of any char in window.

vi. Containers — pick the right one. Don't forget these.

List.

[1, 2, 3]

Ordered row of boxes. Duplicates OK. Indexable.

add.append(x)

find xx in lst O(n) — walks row

empty[]

use fororder, duplicates, position lookup

x in list is slow — for fast lookup reach for a set.

Set.

{1, 2, 3}

Unordered guest list. No duplicates. No index.

add.add(x)

find xx in s O(1) — instant

emptyset() (NOT {} — that's a dict)

use fordedup, "seen X?" check, set math

Items must be immutable. set.add([1,2]) → TypeError. Wrap as tuple.

Dict.

{"a": 1}

Magic notebook. Key → value. Unique keys.

add / setd[k] = v

getd[k] · d.get(k, default)

find keyk in d O(1) — instant

empty{} or dict()

use forcounting, complement-find, grouping

Keys must be immutable. Counting? prefer defaultdict(int) or Counter.

Tuple.

(1, 2, 3)

Ordered, sealed forever. Like a frozen list.

readt[i]

find xx in t O(n)

unpacka, b = (1, 2)

use forset/dict keys · multi-return · fixed group

Can't .append, can't edit. That's the point — it's why sets accept it.

vii. Naming Conventions — Pythonic style (PEP 8)

Variables.

snake_case

Lowercase with underscores. Descriptive. Single letters only in tight loops.

examplestotal_count · max_value · left · mid

constantsMAX_SIZE = 100 — ALL_CAPS

booleansis_valid · has_dup · can_jump

private_internal — underscore prefix

Don't use data, info, temp, obj — too generic. Name what's in it.

Functions.

snake_case verb

Action phrases starting with verbs.

examplescount_chars() · find_pair() · is_palindrome()

findersPrefix with find_, get_, compute_

checkersPrefix with is_, has_, can_

paramsSnake too: def foo(my_arg, max_size):

LeetCode boilerplate often uses camelCase (twoSum, isValid) — match the platform's exception when you submit there.

Classes.

PascalCase

Capital-first noun phrases. The "thing," not the action.

examplesMinStack · LRUCache · Solution

methodsInside class: snake_case (def push(self):)

initdef __init__(self): — dunder = double underscore

attrsself.snake_case — never CamelCase

LC always uses class Solution: as the wrapper. Don't rename it.

Anti-Patterns.

⊘ DON'T

Smells interviewers notice. Avoid them.

noCryptic state names: x, y, val, tmp

noHungarian: strName, intCount

noMixed: firstName → use first_name

noGeneric: data, info, temp, obj

noenumerate when you don't use the index

Names earn their length. i as a loop index is fine. x as a stored variable isn't.

Common interview names — burn these in your fingers

numslist of integers (input)

targetvalue to find / match

resultwhat you return

seenset or dict of visited

countsCounter / frequencies

left, righttwo pointers

midbinary search middle

stacklist used as stack

queuedeque for BFS

heapheapq min-heap

i, j, ktight loop indices

c, chchar in a string

nodeLL or tree node

head, tailLL endpoints

roottree root

visitedgraph DFS/BFS set

Edge Case Sweep — every problem

empty input
single element
all duplicates
all unique
negative numbers
zero mid-sequence
huge input (talk, don't compute)
already-sorted / reverse-sorted
off-by-one at first / last index
no answer exists — what's returned?

Bugs That Bite — scan after coding

0-indexed vs 1-indexed (Two Sum Sorted returns 1-indexed!)
dict.get(c, 0) NOT get(c, 1)
Index vs value: i + nums[L] ✗ — use nums[i] + nums[L]
Wrong pattern: reached for L,R = 0, n-1 on sliding window — both go FORWARD, not converge
Missing inner loop: set up left, right but no while left < right → pointers never move
Reset pointers INSIDE outer loop — otherwise stale state on next anchor
Match branch must advance pointers — elif chain isolates the match case
abs distance vs sum: abs(cur - tgt) < closest_sum ✗ — compare BOTH sides as distance
Scope creep: don't lowercase / clean input if not asked
two-pointer: L < R not <= (no reuse)
binary: low <= high vs < — pick on purpose
mutating list while iterating it (don't)
if not x matches 0, "", [] — use is None
integer division: // not /
heap: Python is min only — negate for max

Things You Say · Things You Don't

→ lean on

"Let me restate…"

"A few clarifying questions…"

"Brute force first, then optimize."

"My invariant here is…"

"Let me trace a small example."

⊘ never

"This is easy."

"I don't remember."

"I'll skip edge cases for now."

"Can you give me a hint?"

PG · 02 / 03

PATTERNS — PRINT LANDSCAPE · CHEATSHEET

PREP CHEATSHEET

i. The growth curves — what each Big-O looks like

Lines reading upward = slower as input grows. Anything below O(n) is fast. Anything above O(n²) is dangerous past n ≈ 1000. O(2ⁿ) is only acceptable when n ≤ 20.

ii. Real numbers — ops at common input sizes

Big-O	n=10	n=100	n=1,000	n=1M
O(1)	1	1	1	1
O(log n)	~3	~7	~10	~20
O(n)	10	100	1,000	1M
O(n log n)	~30	~700	~10K	~20M
O(n²)	100	10K	1M	10¹² ⚠
O(2ⁿ)	1K	10³⁰ ⚠	∞	∞

RULE OF THUMB Roughly 10⁸ ops/sec on a modern judge. So O(n²) at n=10⁴ ≈ 1 sec. O(n²) at n=10⁵ ≈ 100 sec → TLE. Pick your complexity to fit.

iii. Visual mental models — what each class "looks like"

O(1)

Constant

Always one step. No matter how big n is, you do the same fixed work.

O(log n)

Halving

Each step halves the search range. Walk the tree from root to leaf — log₂(n) levels deep.

O(n)

Linear

One pass through every item. Touch n boxes, one at a time.

O(n log n)

Sort + sweep

Sort first, then a single sweep. Sorting dominates — log n levels of merge × n items per level.

O(n²)

Every pair

Every pair (i, j). n rows × n cols — visit every cell. Nested loops over the same input.

O(2ⁿ)

Exponential

Doubles at every level. Try every subset / every decision branch. Use only when n ≤ 20.

iv. Time vs Space — two separate budgets

⏱ TIME

Counts operations. The interviewer asks: "how long does this run?" Each +, comparison, dict lookup = 1 op.

Time grows with the algorithm shape — one loop = O(n), two nested = O(n²), etc.

📦 SPACE

Counts memory. The interviewer asks: "how much extra storage?" Variables, lists, dicts, recursion stack.

Space is O(1) if you only use a few vars. O(n) if you build a structure of n items. Don't count the input itself — only EXTRA memory.

Same algorithm can have different time and space. Two pointers: O(n) time, O(1) space. Hash map of complements: O(n) time, O(n) space. Pick the trade-off the problem allows.

v. The Big-O simplification rules

Drop constants. 5n + 100 → O(n). 3n²/2 → O(n²).

Drop lower-order terms. n² + n → O(n²). The fastest-growing term wins.

Different inputs → different variables. ADD or MULTIPLY.
ADD when inputs are separate: two lists of sizes m and n → O(m + n).
MULTIPLY when one input has a "per-item" cost: n strings each costing k work → O(n · k).
Ex: Group Anagrams = O(n · k log k) — n strings, each sorted in O(k log k). Matrix = O(m · n).

Worst case is the default. "Average" and "best" can be stated separately, but the default is worst.

PG · 03 / 03

COMPLEXITY — VISUAL PRIMER · END.