Nine spreads on how to store data and process it efficiently: Big-O, arrays, hash maps, stacks and queues, trees, graphs, sorting, and dynamic programming. Code is Python.
"A hash map makes the lookup O(1), so the whole thing drops from quadratic to linear time and linear space."
Use the tabs or the ← → keys. Run each snippet and change it.
Big-O describes the shape of growth, ignoring constants. It tells you whether code will survive 10× or 1,000× more data.
| Class | Example | n = 1,000,000 |
|---|---|---|
| O(1) | dict lookup, array index | 1 step |
| O(log n) | binary search | ~20 steps |
| O(n) | scan a list | 1 M |
| O(n log n) | good sorting | ~20 M |
| O(n²) | nested loops over the same list | 10¹²: too slow |
| O(2ⁿ) | naive recursion on subsets | impossible past ~40 |
# O(n²): for each item, scan the rest
def has_dup_slow(xs):
return any(xs[i] == xs[j] for i in range(len(xs)) for j in range(i + 1, len(xs)))
# O(n) time, O(n) space: remember what you've seen
def has_dup_fast(xs):
seen = set()
for x in xs:
if x in seen: return True
seen.add(x)
return False
"The nested loop is quadratic; a set makes it linear at the cost of O(n) extra memory."
# two pointers: does a sorted list contain a pair summing to target? O(n)
def pair_sum(xs, target):
l, r = 0, len(xs) - 1
while l < r:
s = xs[l] + xs[r]
if s == target: return (xs[l], xs[r])
if s < target: l += 1
else: r -= 1
return None
# sliding window: max sum of any k consecutive items. O(n)
def max_window(xs, k):
cur = best = sum(xs[:k])
for i in range(k, len(xs)):
cur += xs[i] - xs[i - k]
best = max(best, cur)
return best
# linked list node + reverse in place
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def reverse(head):
prev = None
while head:
head.next, prev, head = prev, head, head.next
return prev
"Sorted input: two pointers. Contiguous subarray: a sliding window. Both cut a nested loop to one pass."
# Two-sum: find indices i, j with xs[i] + xs[j] == target. O(n) time
def two_sum(xs, target):
idx = {} # value → index
for i, x in enumerate(xs):
if target - x in idx:
return idx[target - x], i
idx[x] = i
# Count frequencies
from collections import Counter, defaultdict
Counter("mississippi") # {'i': 4, 's': 4, 'p': 2, 'm': 1}
# Group anagrams
groups = defaultdict(list)
for w in ["eat", "tea", "tan", "ate", "nat", "bat"]:
groups["".join(sorted(w))].append(w) # key = sorted letters
print(list(groups.values())) # [['eat','tea','ate'], ['tan','nat'], ['bat']]
# Set operations
a, b = {1, 2, 3}, {3, 4}
a & b, a | b, a - b # intersection, union, difference
"I trade O(n) memory for O(1) lookups with a hash map, which brings the whole algorithm to linear time."
# balanced brackets with a stack
def balanced(s):
pairs = {')': '(', ']': '[', '}': '{'}
st = []
for ch in s:
if ch in "([{": st.append(ch)
elif ch in pairs:
if not st or st.pop() != pairs[ch]: return False
return not st
balanced("{[()]}") # True balanced("(]") # False
# queue and priority queue
from collections import deque
import heapq
q = deque([1, 2, 3]); q.append(4); q.popleft() # O(1) both ends
h = []
for x in [5, 1, 8, 3]: heapq.heappush(h, x) # O(log n)
heapq.heappop(h) # → 1, the smallest, O(log n)
heapq.nlargest(2, [5, 1, 8, 3]) # top-k → [8, 5]
"A min-heap gives me the next smallest in logarithmic time, so top-k is n log k."
Recursion = a base case plus a smaller version of the same problem. A balanced BST gives O(log n) search; an unbalanced one degrades to O(n) (so databases use B-trees, languages use red-black trees).
class TreeNode:
def __init__(self, val, left=None, right=None):
self.val, self.left, self.right = val, left, right
def height(n): # O(n)
if n is None: return 0 # base case
return 1 + max(height(n.left), height(n.right))
def search(n, target): # O(h)
while n:
if target == n.val: return True
n = n.left if target < n.val else n.right
return False
def inorder(n):
return inorder(n.left) + [n.val] + inorder(n.right) if n else []
from collections import deque
def level_order(root): # BFS with a queue
out, q = [], deque([root] if root else [])
while q:
row = []
for _ in range(len(q)):
n = q.popleft(); row.append(n.val)
q.extend(c for c in (n.left, n.right) if c)
out.append(row)
return out
"Base case, recurse on children, combine. It's O(n) since each node is visited once."
from collections import deque
import heapq
graph = {"A": ["B","C"], "B": ["A","D"], "C": ["A","E"], "D": ["B","F"], "E": ["C","F"], "F": ["D","E"]}
def bfs_shortest(g, start, goal): # fewest hops. O(V+E)
q, seen = deque([(start, [start])]), {start}
while q:
node, path = q.popleft()
if node == goal: return path
for nb in g[node]:
if nb not in seen:
seen.add(nb); q.append((nb, path + [nb]))
def dfs(g, node, seen=None): # O(V+E): connectivity, cycles, components
seen = seen or set()
seen.add(node)
for nb in g[node]:
if nb not in seen: dfs(g, nb, seen)
return seen
def dijkstra(g, src): # weighted, non-negative. O((V+E) log V)
dist = {src: 0}; pq = [(0, src)]
while pq:
d, u = heapq.heappop(pq)
if d > dist.get(u, float("inf")): continue
for v, w in g[u]: # g[u] = [(neighbor, weight), …]
nd = d + w
if nd < dist.get(v, float("inf")):
dist[v] = nd; heapq.heappush(pq, (nd, v))
return dist
"BFS for fewest hops, Dijkstra for weighted shortest paths, topological sort for dependencies."
def merge_sort(xs):
if len(xs) <= 1: return xs
mid = len(xs) // 2
a, b = merge_sort(xs[:mid]), merge_sort(xs[mid:])
out, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] <= b[j]: out.append(a[i]); i += 1 # <= keeps it stable
else: out.append(b[j]); j += 1
return out + a[i:] + b[j:]
def binary_search(xs, target): # O(log n), xs must be sorted
lo, hi = 0, len(xs) - 1
while lo <= hi:
mid = (lo + hi) // 2
if xs[mid] == target: return mid
if xs[mid] < target: lo = mid + 1
else: hi = mid - 1
return -1
import bisect
bisect.bisect_left([1, 3, 5, 7], 5) # library version → 2
people = [("Ama", 31), ("Kofi", 27), ("Esi", 31)]
sorted(people, key=lambda p: (-p[1], p[0])) # by age desc, then name
"Sort first, then binary search or sweep. The sort dominates at O(n log n)."
from functools import cache
@cache # memoization in one line
def fib(n): # O(n) instead of O(2ⁿ)
return n if n < 2 else fib(n - 1) + fib(n - 2)
def coin_change(coins, amount): # fewest coins to make `amount`. O(amount × coins)
INF = float("inf")
dp = [0] + [INF] * amount # dp[a] = fewest coins for amount a
for a in range(1, amount + 1):
for c in coins:
if c <= a: dp[a] = min(dp[a], dp[a - c] + 1)
return dp[amount] if dp[amount] != INF else -1
coin_change([1, 5, 10, 25], 63) # 6 (25+25+10+1+1+1)
def lcs(a, b): # longest common subsequence. O(len(a) × len(b))
dp = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
for i in range(1, len(a) + 1):
for j in range(1, len(b) + 1):
dp[i][j] = dp[i-1][j-1] + 1 if a[i-1] == b[j-1] else max(dp[i-1][j], dp[i][j-1])
return dp[-1][-1]
def max_meetings(intervals): # greedy: always take the one that ends earliest
end, count = float("-inf"), 0
for s, e in sorted(intervals, key=lambda x: x[1]):
if s >= end: count += 1; end = e
return count
"Overlapping subproblems and optimal substructure, so DP: state, recurrence, base case."
# a tiny test harness
def check(fn, cases):
for args, expected in cases:
got = fn(*args)
print("ok " if got == expected else "FAIL", fn.__name__, args, "→", got)
check(two_sum, [(([2, 7, 11, 15], 9), (0, 1)), (([3, 3], 6), (0, 1))])
"Brute force first, then I remove the repeated work with the right structure and state the complexity."