Complexity & Problem Patterns

Pattern recognition is the real skill in DSA interviews. Most problems map to one of ~15 patterns. Once you see the pattern, the solution follows.

Time Complexity Cheat Sheet:
• O(1)       → hash lookup, array index, stack push/pop
• O(log n)   → binary search, balanced BST ops, heap ops
• O(n)       → linear scan, two pointers, sliding window
• O(n log n) → sorting, heap of n elements
• O(n²)      → nested loops, brute force pairs
• O(2ⁿ)      → subset enumeration, exponential recursion

Space Complexity:
• O(1)    → two pointers, in-place ops
• O(n)    → hash map, recursion stack, output array
• O(n²)   → 2D DP table

Pattern → Algorithm mapping (memorize this table):
• "K largest/smallest"       → Heap
• "Subarray/substring"       → Sliding Window
• "Sorted array pairs"       → Two Pointers
• "Tree path/structure"      → DFS recursion
• "Shortest path"            → BFS
• "Count ways/combinations"  → DP
• "Connected components"     → Union-Find or DFS
• "Find duplicate/missing"   → XOR or hash set

1import time
2import functools
3
4# ── Complexity comparison — actually measure it ───────────────────
5def time_it(fn, *args):
6    start = time.perf_counter()
7    result = fn(*args)
8    return time.perf_counter() - start
9
10n = 10000
11arr = list(range(n))
12
13# O(1) — hash lookup
14d = {i: i for i in arr}
15print(f"O(1)  hash  : {time_it(lambda: d[n//2]):.8f}s")
16
17# O(log n) — binary search
18import bisect
19print(f"O(logn) bs  : {time_it(bisect.bisect_left, arr, n//2):.8f}s")
20
21# O(n) — linear scan
22print(f"O(n)  scan  : {time_it(lambda: n//2 in arr):.8f}s")
23
24# O(n log n) — sort
25import random
26arr_rand = list(range(n)); random.shuffle(arr_rand)
27print(f"O(nlogn) sort: {time_it(sorted, arr_rand):.8f}s")
28
29# ── Backtracking template (permutations) ─────────────────────────
30def permutations(nums: list[int]) -> list[list[int]]:
31    result = []
32    def backtrack(path, remaining):
33        if not remaining:
34            result.append(path[:])
35            return
36        for i in range(len(remaining)):
37            path.append(remaining[i])
38            backtrack(path, remaining[:i] + remaining[i+1:])
39            path.pop()              # undo choice ← key backtracking step
40    backtrack([], nums)
41    return result
42
43# ── Union-Find (Disjoint Set) — connected components ─────────────
44class UnionFind:
45    def __init__(self, n):
46        self.parent = list(range(n))
47        self.rank   = [0] * n
48
49    def find(self, x):
50        if self.parent[x] != x:
51            self.parent[x] = self.find(self.parent[x])  # path compression
52        return self.parent[x]
53
54    def union(self, x, y) -> bool:
55        px, py = self.find(x), self.find(y)
56        if px == py: return False   # already connected
57        if self.rank[px] < self.rank[py]: px, py = py, px
58        self.parent[py] = px
59        if self.rank[px] == self.rank[py]: self.rank[px] += 1
60        return True
61
62# ── Number of provinces (union-find) ─────────────────────────────
63def find_circle_num(isConnected: list[list[int]]) -> int:
64    n  = len(isConnected)
65    uf = UnionFind(n)
66    for i in range(n):
67        for j in range(i+1, n):
68            if isConnected[i][j]: uf.union(i, j)
69    return len({uf.find(i) for i in range(n)})
70
71print(permutations([1,2,3]))          # all 6 permutations
72print(find_circle_num([[1,1,0],[1,1,0],[0,0,1]]))  # 2