#The cheat sheet

Every template here was executed against test cases before publishing, including 300 randomised binary-search cases checked against Python's bisect. Cheat sheets are usually where off-by-ones go to hide.

#1 · Constraints → algorithm

The fastest read in the room. The constraint tells you the intended complexity, and the complexity tells you the algorithm.

If n ≤ 20 and the question says "return all", the answer is exponential and that is intended. Do not look for a clever polynomial solution.

#2 · Cue → pattern

#3 · The templates

Type these from memory. All verified.

#Binary search — exact

def search(a, target):
    lo, hi = 0, len(a) - 1          # CLOSED interval
    while lo <= hi:                 # <= because hi is inclusive
        mid = lo + (hi - lo) // 2   # avoids overflow in Java/C++
        if a[mid] == target: return mid
        if a[mid] < target: lo = mid + 1
        else:                hi = mid - 1
    return -1

#Binary search — leftmost / rightmost

The two you actually need. Half-open interval; the loop shape differs from the exact version and mixing them is the classic bug.

def left_bound(a, t):               # == bisect_left
    lo, hi = 0, len(a)              # hi = n, HALF-OPEN
    while lo < hi:                  # < not <=
        mid = lo + (hi - lo) // 2
        if a[mid] < t: lo = mid + 1
        else:          hi = mid     # NOT mid-1
    return lo

def right_bound(a, t):              # == bisect_right
    lo, hi = 0, len(a)
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if a[mid] <= t: lo = mid + 1    # the ONLY change: <= not <
        else:           hi = mid
    return lo

left and right differ by one character — < versus <=. Learn the pair together; learning one alone guarantees you derive the other wrongly under pressure.

#Binary search on the answer

The pattern that looks like nothing else. Use when the question is "minimise the maximum" or "maximise the minimum".

def min_capacity(weights, days):
    def feasible(cap):              # monotonic: true for all larger caps
        d, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                d += 1; cur = 0
            cur += w
        return d <= days

    lo, hi = max(weights), sum(weights)   # bounds must be VALID answers
    while lo < hi:
        mid = lo + (hi - lo) // 2
        if feasible(mid): hi = mid        # keep searching lower
        else:             lo = mid + 1
    return lo

Three questions to ask: what am I searching over (not the array — the answer)? Is feasible monotonic? Are my bounds valid answers?

#Sliding window — variable size

def longest_unique(s):
    seen = {}                        # char -> last index
    best = left = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1      # >= left: never move `left` BACKWARDS
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

seen[ch] >= left is the whole difficulty. On "abba", when the second a arrives its stored index is 0, which is behind left. Without the guard you jump left backwards and get 3 instead of 2.

#Two pointers — opposite ends

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target: return [lo, hi]
        if s < target:  lo += 1      # need bigger
        else:           hi -= 1      # need smaller
    return []

#Monotonic stack — next greater

def next_greater(nums):
    res, st = [-1] * len(nums), []   # st holds INDICES
    for i, n in enumerate(nums):
        while st and nums[st[-1]] < n:
            res[st.pop()] = n        # n is the answer for everything popped
        st.append(i)
    return res

Store indices, not values — you almost always need the position, and can get the value from it. For distance problems (LC 739) the answer is i - j.

#BFS on a grid

from collections import deque

def shortest_path(grid):
    R, C = len(grid), len(grid[0])
    q = deque([(0, 0, 1)])
    seen = {(0, 0)}                  # mark visited ON PUSH, not on pop
    while q:
        r, c, d = q.popleft()
        if (r, c) == (R - 1, C - 1): return d
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and grid[nr][nc] == 0 \
               and (nr, nc) not in seen:
                seen.add((nr, nc))
                q.append((nr, nc, d + 1))
    return -1

Mark visited when you push, not when you pop. Popping lets the same cell enter the queue many times before it is first processed, which turns O(V+E) into something much worse.

#Backtracking

def backtrack(path, choices):
    if is_complete(path):
        results.append(path[:])      # COPY -- path is mutated after this
        return
    for choice in choices:
        if not valid(choice, path): continue   # prune
        path.append(choice)          # choose
        backtrack(path, next_choices)# explore
        path.pop()                   # UNDO

#DP — 1D, rolling variables

def rob(nums):
    prev = cur = 0
    for n in nums:
        prev, cur = cur, max(cur, prev + n)
    return cur

Write the O(n)-space table first, then compress. Compressing before the recurrence is correct is how you produce something that is fast and wrong.

#Union-Find

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0]*n; self.count = n
    def find(self, x):
        if self.p[x] != x: self.p[x] = self.find(self.p[x])   # compress
        return self.p[x]
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False        # already joined -> a CYCLE edge
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        self.count -= 1
        return True

#4 · Complexity

Sorting is O(n log n). If your solution is already O(n log n), sorting is free — say so.

Recursion space is the call depth, and it is separate from time. The subsets tree is O(2ⁿ) time but only O(n) stack.

#5 · Python ↔ Java

Four that cause real bugs: a - b in a Java comparator overflows — use Integer.compare. Java % keeps the dividend's sign — normalise with ((x % k) + k) % k. -7 // 2 is -4 in Python, -3 in Java. Python tuple comparison falls through to the next element — add a tiebreaker when heaping non-comparable objects.

#6 · Bugs that actually cost you

#7 · Before you type

[ ] Restate the problem in one sentence
[ ] Ask: duplicates? negatives? empty? sorted? size?
[ ] State the brute force AND its complexity
[ ] Name the pattern out loud, and why
[ ] Say the target complexity before coding
[ ] Walk one small example by hand
[ ] Code it
[ ] Trace the example through your code, out loud
[ ] Check: empty, single element, all-same, largest input

Stating the brute force first is free marks. It shows you understand the problem before optimising it, and it gives you a correctness baseline to compare against.

#8 · The 10 problems that teach the most

If you have one evening:

These ten cover eight patterns. If you can re-derive all ten cold, you can attempt most of an interview loop.