A practical, example-driven reference for the data structures you'll use constantly, plus the recurring patterns (sum, min/max, 2D arrays, prefix sums, sliding window, etc.) that show up in almost every problem.
- 1. Arrays & Lists
- 2. Stack
- 3. Queue
- 4. Deque (Double-Ended Queue)
- 5. Heap / Priority Queue
- 6. Map (Dictionary / HashMap)
- 7. Set
- 8. Linked List
- 9. Trees
- 10. Graphs
- 11. Sorting & Searching Cheatsheet
- 12. Big-O Cheat Sheet
- 13. General Tips & Tricks
Python's built-in list is a dynamic array. It's the backbone of most DSA work.
arr = [5, 3, 8, 1, 9]
arr.append(10) # add to end -> O(1) amortized
arr.insert(0, 100) # insert at index -> O(n)
arr.pop() # remove & return last -> O(1)
arr.pop(0) # remove & return first -> O(n)
arr.remove(8) # remove first occurrence of value -> O(n)
# Slicing (never mutates the original)
first_three = arr[:3]
last_two = arr[-2:]
reversed_arr = arr[::-1]
every_other = arr[::2]
# Swap without a temp variable
arr[0], arr[1] = arr[1], arr[0]Tip: arr[::-1] is the idiomatic reverse — O(n) but very fast (implemented in C).
# 1D array of size n filled with 0
zeros = [0] * 10
# ⚠️ Common trap: for MUTABLE elements (lists), * copies references!
wrong = [[0] * 3] * 3 # all 3 rows are the SAME list object
wrong[0][0] = 99 # mutates every row!
# Correct way: fresh list per row
grid = [[0] * 3 for _ in range(3)]
# Fill with a range
nums = list(range(1, 11)) # [1, 2, ..., 10]
# Fill with a formula (list comprehension)
squares = [i * i for i in range(10)]
# Fill with input/dynamic values
n = 5
vals = [int(x) for x in input().split()] # reading n ints from stdinrows, cols = 4, 5
# Correct initialization (no shared references)
matrix = [[0] * cols for _ in range(rows)]
# Access
matrix[1][2] = 7
# Iterate row by row
for r in range(rows):
for c in range(cols):
print(matrix[r][c], end=" ")
print()
# Iterate with enumerate (get both index & value)
for r, row in enumerate(matrix):
for c, val in enumerate(row):
...
# Transpose a matrix
transposed = [list(row) for row in zip(*matrix)]
# Rotate 90° clockwise
rotated_cw = [list(row) for row in zip(*matrix[::-1])]
# Rotate 90° counter-clockwise
rotated_ccw = [list(row) for row in zip(*matrix)][::-1]
# Flatten a 2D array to 1D
flat = [val for row in matrix for val in row]
# or:
import itertools
flat2 = list(itertools.chain.from_iterable(matrix))Tip — 4-directional / 8-directional traversal (grid problems, flood fill, BFS on grids):
DIRS_4 = [(-1, 0), (1, 0), (0, -1), (0, 1)] # up, down, left, right
DIRS_8 = DIRS_4 + [(-1, -1), (-1, 1), (1, -1), (1, 1)] # + diagonals
def in_bounds(r, c, rows, cols):
return 0 <= r < rows and 0 <= c < cols
for dr, dc in DIRS_4:
nr, nc = r + dr, c + dc
if in_bounds(nr, nc, rows, cols):
...x, y, z = 3, 4, 5
# Correct: nested comprehensions, never `* z` on mutable rows
cube = [[[0] * z for _ in range(y)] for _ in range(x)]
cube[1][2][3] = 42
# Common use case: DP over (index, remaining_capacity, state)
dp = [[[-1] * (k + 1) for _ in range(cap + 1)] for _ in range(n + 1)]nums = [4, 2, 9, -3, 7]
total = sum(nums) # 19
lowest = min(nums) # -3
highest = max(nums) # 9
# With a key function
words = ["apple", "hi", "banana"]
longest = max(words, key=len) # "banana"
shortest = min(words, key=len) # "hi"
# Index of min/max (no built-in — do it manually or with enumerate)
max_idx = max(range(len(nums)), key=lambda i: nums[i])
# Sum of a 2D array
grid_sum = sum(sum(row) for row in matrix)
# Row-wise and column-wise sums
row_sums = [sum(row) for row in matrix]
col_sums = [sum(col) for col in zip(*matrix)]
# Running max/min while scanning (classic pattern — Kadane's, stock problems)
def max_subarray_sum(nums):
best = cur = nums[0]
for x in nums[1:]:
cur = max(x, cur + x) # extend or restart
best = max(best, cur)
return best
# Second largest without sorting -> O(n)
def second_largest(nums):
first = second = float("-inf")
for x in nums:
if x > first:
first, second = x, first
elif first > x > second:
second = x
return secondTip: sum(), min(), max() all accept generators directly — no need to build a list first:
sum(x * x for x in nums) is faster and uses O(1) extra memory vs sum([x*x for x in nums]).
Precompute cumulative sums to answer range-sum queries in O(1) after O(n) preprocessing.
nums = [3, 1, 4, 1, 5, 9, 2, 6]
prefix = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
prefix[i + 1] = prefix[i] + x
def range_sum(l, r): # inclusive range [l, r]
return prefix[r + 1] - prefix[l]
range_sum(2, 5) # 4+1+5+9 = 19
# Using itertools (built-in, C-optimized)
from itertools import accumulate
prefix2 = list(accumulate(nums, initial=0))2D prefix sum (submatrix sum in O(1)):
def build_prefix_2d(matrix):
rows, cols = len(matrix), len(matrix[0])
P = [[0] * (cols + 1) for _ in range(rows + 1)]
for r in range(rows):
for c in range(cols):
P[r+1][c+1] = matrix[r][c] + P[r][c+1] + P[r+1][c] - P[r][c]
return P
def submatrix_sum(P, r1, c1, r2, c2): # inclusive corners
return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]# Two pointers: pair with target sum in a SORTED array -> O(n)
def two_sum_sorted(nums, target):
lo, hi = 0, len(nums) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s == target:
return (lo, hi)
elif s < target:
lo += 1
else:
hi -= 1
return None
# Sliding window: max sum of a subarray of size k -> O(n)
def max_sum_window(nums, k):
window_sum = sum(nums[:k])
best = window_sum
for i in range(k, len(nums)):
window_sum += nums[i] - nums[i - k] # slide: add new, drop old
best = max(best, window_sum)
return best
# Variable-size window: smallest subarray with sum >= target
def min_subarray_len(target, nums):
lo, cur, best = 0, 0, float("inf")
for hi, x in enumerate(nums):
cur += x
while cur >= target:
best = min(best, hi - lo + 1)
cur -= nums[lo]
lo += 1
return best if best != float("inf") else 0LIFO — Last In, First Out. Use a plain Python list; append/pop from the end are O(1).
stack = []
stack.append(1)
stack.append(2)
stack.append(3)
top = stack.pop() # 3
peek = stack[-1] # 2 (look without removing)
is_empty = not stackClassic use cases:
# Valid parentheses
def is_valid(s):
pairs = {')': '(', ']': '[', '}': '{'}
stack = []
for ch in s:
if ch in "([{":
stack.append(ch)
elif ch in pairs:
if not stack or stack.pop() != pairs[ch]:
return False
return not stack
# Next Greater Element (monotonic decreasing stack) -> O(n)
def next_greater(nums):
res = [-1] * len(nums)
stack = [] # stores indices
for i, x in enumerate(nums):
while stack and nums[stack[-1]] < x:
res[stack.pop()] = x
stack.append(i)
return res
# Evaluate Reverse Polish Notation
def eval_rpn(tokens):
stack = []
ops = {'+': lambda a, b: a + b, '-': lambda a, b: a - b,
'*': lambda a, b: a * b, '/': lambda a, b: int(a / b)}
for t in tokens:
if t in ops:
b, a = stack.pop(), stack.pop()
stack.append(ops[t](a, b))
else:
stack.append(int(t))
return stack[0]Tips & tricks:
- Never use
list.pop(0)as a stack op by mistake — that's O(n), not the stack's top. - Monotonic stacks (increasing or decreasing) are the go-to for "next greater/smaller element", histogram/largest-rectangle problems, and daily-temperature style problems.
collections.dequealso works as a stack (append/pop) and is slightly faster for very large data.
FIFO — First In, First Out. Don't use a plain list for this — pop(0) is O(n).
Use collections.deque instead — O(1) on both ends.
from collections import deque
q = deque()
q.append(1) # enqueue
q.append(2)
q.append(3)
front = q.popleft() # dequeue -> 1
is_empty = not qClassic use case — BFS:
def bfs(graph, start):
visited = {start}
q = deque([start])
order = []
while q:
node = q.popleft()
order.append(node)
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
q.append(nei)
return order
# BFS on a grid (shortest path in unweighted grid)
def shortest_path_grid(grid, start, end):
rows, cols = len(grid), len(grid[0])
q = deque([(start, 0)])
visited = {start}
while q:
(r, c), dist = q.popleft()
if (r, c) == end:
return dist
for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
nr, nc = r + dr, c + dc
if 0 <= nr < rows and 0 <= nc < cols and (nr,nc) not in visited and grid[nr][nc] != 1:
visited.add((nr, nc))
q.append(((nr, nc), dist + 1))
return -1
# For priority-based processing, use a heap instead (see Section 5)There's also queue.Queue (thread-safe, for multithreading — heavier, rarely needed for plain algorithms).
Push/pop from both ends in O(1). Use for sliding-window problems, palindrome checks, and as a faster stack/queue.
from collections import deque
dq = deque([1, 2, 3])
dq.append(4) # [1, 2, 3, 4]
dq.appendleft(0) # [0, 1, 2, 3, 4]
dq.pop() # removes 4
dq.popleft() # removes 0
dq.rotate(1) # rotate right by 1
dq.rotate(-1) # rotate left by 1
# Fixed-size sliding window (auto-evicts oldest) — great for "last k elements"
window = deque(maxlen=3)
for x in [1, 2, 3, 4, 5]:
window.append(x) # older items drop off automaticallyClassic use case — Sliding Window Maximum (monotonic deque) -> O(n):
def max_sliding_window(nums, k):
dq = deque() # stores indices, values in decreasing order
res = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] < x:
dq.pop()
dq.append(i)
if dq[0] <= i - k: # window has slid past this index
dq.popleft()
if i >= k - 1:
res.append(nums[dq[0]])
return resPython's heapq implements a min-heap on top of a plain list. No max-heap built in — negate values instead.
import heapq
h = []
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 8)
smallest = heapq.heappop(h) # 1
peek = h[0] # smallest without removing
# Build a heap from an existing list in O(n) (faster than n pushes -> O(n log n))
nums = [5, 1, 8, 3, 9]
heapq.heapify(nums)
# Max-heap trick: negate on push, negate again on pop
max_h = []
for x in nums:
heapq.heappush(max_h, -x)
largest = -heapq.heappop(max_h)
# k largest / k smallest without a full sort -> O(n log k)
k_largest = heapq.nlargest(3, nums)
k_smallest = heapq.nsmallest(3, nums)
# Push tuples for priority queues (e.g. (distance, node) for Dijkstra)
pq = []
heapq.heappush(pq, (0, "start"))
heapq.heappush(pq, (5, "b"))
dist, node = heapq.heappop(pq) # smallest distance popped firstClassic use cases:
# Kth largest element in an array -> O(n log k)
def kth_largest(nums, k):
heap = nums[:k]
heapq.heapify(heap)
for x in nums[k:]:
if x > heap[0]:
heapq.heapreplace(heap, x) # pop-then-push in one call, faster than 2 ops
return heap[0]
# Merge k sorted lists -> O(n log k)
def merge_k_sorted(lists):
h = [(lst[0], i, 0) for i, lst in enumerate(lists) if lst]
heapq.heapify(h)
result = []
while h:
val, i, j = heapq.heappop(h)
result.append(val)
if j + 1 < len(lists[i]):
heapq.heappush(h, (lists[i][j+1], i, j+1))
return result
# Dijkstra's shortest path
def dijkstra(graph, start):
dist = {start: 0}
pq = [(0, start)]
while pq:
d, node = heapq.heappop(pq)
if d > dist.get(node, float("inf")):
continue # stale entry, skip
for nei, weight in graph[node]:
nd = d + weight
if nd < dist.get(nei, float("inf")):
dist[nei] = nd
heapq.heappush(pq, (nd, nei))
return distTips & tricks:
- Tuples compare element-by-element, so
(priority, tiebreaker, item)is the standard pattern to avoid comparing non-comparable items when priorities tie. heapq.heapreplace(h, x)(pop then push) andheapq.heappushpop(h, x)(push then pop) are both faster than doing the two ops separately — pick based on whetherxshould be compared before or after insertion.- For a true max-heap with custom objects, wrap with
__lt__reversed, or just negate numeric keys.
Python's dict — average O(1) insert/lookup/delete. Insertion-ordered since Python 3.7+.
d = {"a": 1, "b": 2}
d["c"] = 3 # insert/update
val = d.get("z", 0) # safe lookup with default -> avoids KeyError
exists = "a" in d # O(1) membership check
del d["a"] # remove
d.pop("b", None) # remove safely (no error if missing)
for key, value in d.items():
...
for key in d.keys():
...
for value in d.values():
...Frequency counting — the #1 use case:
from collections import Counter, defaultdict
words = ["a", "b", "a", "c", "b", "a"]
# Method 1: Counter (fastest, cleanest)
freq = Counter(words) # Counter({'a': 3, 'b': 2, 'c': 1})
most_common = freq.most_common(2) # [('a', 3), ('b', 2)]
# Method 2: defaultdict (when you need custom accumulation logic)
freq2 = defaultdict(int)
for w in words:
freq2[w] += 1
# Grouping (e.g. anagrams) with defaultdict(list)
groups = defaultdict(list)
for word in ["eat", "tea", "tan", "ate", "nat", "bat"]:
key = "".join(sorted(word))
groups[key].append(word)Classic use cases:
# Two Sum -> O(n)
def two_sum(nums, target):
seen = {} # value -> index
for i, x in enumerate(nums):
complement = target - x
if complement in seen:
return (seen[complement], i)
seen[x] = i
return None
# First non-repeating character
def first_unique(s):
freq = Counter(s)
for i, ch in enumerate(s):
if freq[ch] == 1:
return i
return -1Tips & tricks:
dict.get(key, default)avoidsKeyErrorand is faster thantry/exceptfor common cases.defaultdictremoves boilerplateif key not in d: d[key] = ...checks entirely.- Keys must be hashable — lists can't be dict keys; use
tuple()to convert (common for grid coords or multi-value keys:d[(r, c)] = value). dictmaintains insertion order — useful for LRU-style caches (OrderedDict/dict.move_to_end).Countersupports set-like operators:c1 + c2,c1 - c2,c1 & c2(min counts),c1 | c2(max counts).
Unordered collection of unique, hashable elements. Average O(1) add/remove/membership check.
s = {1, 2, 3}
s.add(4)
s.remove(2) # KeyError if missing
s.discard(9) # no error if missing — safer
exists = 3 in s # O(1)
# Set algebra
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
union = a | b # {1,2,3,4,5,6}
intersection = a & b # {3,4}
difference = a - b # {1,2}
symmetric = a ^ b # {1,2,5,6} (in one but not both)
# Deduplicate while preserving nothing about order
unique_vals = list(set([3, 1, 2, 3, 1]))
# Deduplicate while PRESERVING order (dict trick, Python 3.7+)
unique_ordered = list(dict.fromkeys([3, 1, 2, 3, 1])) # [3, 1, 2]Classic use cases:
# Detect duplicates -> O(n)
def has_duplicates(nums):
return len(nums) != len(set(nums))
# Longest consecutive sequence -> O(n)
def longest_consecutive(nums):
num_set = set(nums)
best = 0
for x in num_set:
if x - 1 not in num_set: # only start counting from sequence starts
length = 1
while x + length in num_set:
length += 1
best = max(best, length)
return best
# Intersection of two arrays
def intersection(a, b):
return list(set(a) & set(b))Tips & tricks:
frozensetis the hashable/immutable version — usable as a dict key or set element.- Checking membership in a
set(O(1)) instead of alist(O(n)) is one of the single biggest easy wins in optimizing brute-force solutions. - Sets have no guaranteed order — don't rely on iteration order for output.
Not built into Python, but frequently implemented manually for interview-style problems.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def build_linked_list(values):
dummy = ListNode()
cur = dummy
for v in values:
cur.next = ListNode(v)
cur = cur.next
return dummy.next
def print_linked_list(head):
vals = []
while head:
vals.append(head.val)
head = head.next
print(" -> ".join(map(str, vals)))
# Reverse a linked list -> O(n)
def reverse_list(head):
prev = None
while head:
nxt = head.next
head.next = prev
prev = head
head = nxt
return prev
# Detect a cycle — Floyd's Tortoise & Hare -> O(n), O(1) space
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Find middle node (same slow/fast technique)
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slowTip: A dummy head node (dummy = ListNode(); dummy.next = head) removes edge-case handling
for operations that might modify the head (delete, merge, reverse-in-range).
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
# DFS traversals (recursive)
def inorder(root): # left, root, right — sorted order for BST
return inorder(root.left) + [root.val] + inorder(root.right) if root else []
def preorder(root): # root, left, right
return [root.val] + preorder(root.left) + preorder(root.right) if root else []
def postorder(root): # left, right, root
return postorder(root.left) + postorder(root.right) + [root.val] if root else []
# BFS traversal (level order) -> use deque
from collections import deque
def level_order(root):
if not root:
return []
result, q = [], deque([root])
while q:
level = []
for _ in range(len(q)):
node = q.popleft()
level.append(node.val)
if node.left: q.append(node.left)
if node.right: q.append(node.right)
result.append(level)
return result
# Max depth
def max_depth(root):
if not root:
return 0
return 1 + max(max_depth(root.left), max_depth(root.right))
# Validate BST
def is_valid_bst(root, lo=float("-inf"), hi=float("inf")):
if not root:
return True
if not (lo < root.val < hi):
return False
return is_valid_bst(root.left, lo, root.val) and is_valid_bst(root.right, root.val, hi)Tip: Level order (BFS) is the natural fit whenever a problem mentions "levels", "depth", or "minimum steps" in a tree. DFS is natural for path-sum / subtree problems.
Represent as an adjacency list — a dict mapping node → list of neighbors (or (neighbor, weight)).
from collections import defaultdict, deque
graph = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 2), (2, 3)]
for u, v in edges:
graph[u].append(v)
graph[v].append(u) # omit this line for a directed graph
# DFS (recursive)
def dfs(graph, node, visited=None):
if visited is None:
visited = set()
visited.add(node)
for nei in graph[node]:
if nei not in visited:
dfs(graph, nei, visited)
return visited
# DFS (iterative, avoids recursion-limit issues on large graphs)
def dfs_iterative(graph, start):
visited, stack = set(), [start]
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
stack.extend(graph[node])
return visited
# BFS -> shortest path in unweighted graph
def bfs(graph, start):
visited, q = {start}, deque([start])
dist = {start: 0}
while q:
node = q.popleft()
for nei in graph[node]:
if nei not in visited:
visited.add(nei)
dist[nei] = dist[node] + 1
q.append(nei)
return dist
# Topological sort (Kahn's algorithm, BFS-based) -> for DAGs
def topo_sort(graph, num_nodes):
indegree = [0] * num_nodes
for u in graph:
for v in graph[u]:
indegree[v] += 1
q = deque([n for n in range(num_nodes) if indegree[n] == 0])
order = []
while q:
node = q.popleft()
order.append(node)
for nei in graph[node]:
indegree[nei] -= 1
if indegree[nei] == 0:
q.append(nei)
return order if len(order) == num_nodes else [] # empty = cycle detectedTips & tricks:
- Weighted graph → Dijkstra (heap, Section 5). Unweighted graph → plain BFS gives shortest path.
- Track
visitedexplicitly for graphs (unlike trees, cycles mean you can revisit nodes forever). - Union-Find (Disjoint Set Union) is the go-to for connectivity / cycle-detection in undirected graphs — see snippet below.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected -> would form a cycle
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return Truenums = [5, 2, 9, 1, 5, 6]
nums.sort() # in-place, O(n log n) — Timsort
sorted_copy = sorted(nums) # returns new list, original untouched
nums.sort(reverse=True) # descending
nums.sort(key=lambda x: -x) # custom key (equivalent here)
# Sort by multiple criteria: primary asc, secondary desc
people = [("Alice", 30), ("Bob", 25), ("Eve", 30)]
people.sort(key=lambda p: (p[1], -ord(p[0][0])))
# Binary search (array MUST be sorted) -> O(log n)
import bisect
idx = bisect.bisect_left(nums_sorted, target) # leftmost insertion point
idx2 = bisect.bisect_right(nums_sorted, target) # rightmost insertion point
bisect.insort(nums_sorted, target) # insert while keeping sorted, O(n)
def binary_search(arr, target):
lo, hi = 0, len(arr) - 1
while lo <= hi:
mid = (lo + hi) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1| Structure | Access | Search | Insert | Delete | Notes |
|---|---|---|---|---|---|
list (array) |
O(1) | O(n) | O(1) end / O(n) front | O(1) end / O(n) front | Use deque for front ops |
deque |
O(n) | O(n) | O(1) both ends | O(1) both ends | Best for queues/stacks |
dict (hashmap) |
O(1) avg | O(1) avg | O(1) avg | O(1) avg | Worst case O(n), rare |
set |
— | O(1) avg | O(1) avg | O(1) avg | Same hashing caveats |
heapq (heap) |
O(1) min | O(n) | O(log n) | O(log n) | Min-heap only |
| Balanced BST | O(log n) | O(log n) | O(log n) | O(log n) | Not built-in in Python |
| Linked List | O(n) | O(n) | O(1) at known node | O(1) at known node | No random access |
- Pick the container by the operation you do most. Frequent front removal →
deque, notlist. Frequent membership checks →set/dict, notlist. enumerate()beats manual indexing.for i, x in enumerate(arr):is clearer and just as fast asfor i in range(len(arr)): x = arr[i].zip()is your friend for parallel iteration and matrix transposition.for a, b in zip(list1, list2):avoids index bugs entirely.- Avoid
list * nfor nested/mutable structures — it shares references. Always use a comprehension for 2D/3D array initialization. collectionsmodule is underused —Counter,defaultdict,deque,OrderedDict,namedtuplesolve 80% of "I need a custom structure" urges.- Negative indexing & slicing replace a lot of manual loops:
arr[-1](last element),arr[-k:](last k elements),arr[:-1](all but last). math.inf/float("inf")are cleaner than magic large numbers for initializing min/max trackers.- Memoization:
functools.lru_cache(maxsize=None)turns a recursive function into a memoized one in one line — huge for DP problems.from functools import lru_cache @lru_cache(maxsize=None) def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)
itertoolsfor combinatorics:permutations,combinations,product,accumulate,groupby— implement classic patterns without hand-rolled loops.- Bit tricks:
n & (n-1)clears the lowest set bit (useful for counting set bits / power-of-2 checks);n & 1checks even/odd;1 << kfor powers of 2 and bitmask DP. - Watch mutable default arguments —
def f(cache={}):reuses the same dict across calls. UseNoneand initialize inside the function instead. - Profile before optimizing. For DSA-style code, the biggest wins are almost always about picking the right data structure (O(n) → O(1) lookup), not micro-optimizing syntax.