Python DSA — Interview & Competition Reference

Data structures, patterns, graphs, DP, and competition tricks. Companion to the SDE3 reference.

Data structures Patterns Graphs & trees DP Python tricks Complexity ref

Core built-ins

DS list — dynamic array

Use as a stack. Never use list.pop(0) or list.insert(0,x) for queue ops — both are O(n).

a = [1, 2, 3]
a.append(4)       # O(1) amortized
a.pop()           # O(1) — end only
a.pop(0)          # O(n) — don't use as queue!
a.insert(i, x)    # O(n)
a[i:j]            # O(k) slice

import bisect
bisect.bisect_left(a, x)    # O(log n) — sorted list only
bisect.insort(a, x)         # insert and keep sorted

DS collections.deque

O(1) on both ends. Always use for BFS queues. maxlen makes a circular buffer — useful for sliding window eviction.

from collections import deque
dq = deque([1, 2, 3])
dq.append(4)         # right O(1)
dq.appendleft(0)     # left  O(1)
dq.pop()             # right O(1)
dq.popleft()         # left  O(1)
dq.rotate(k)         # rotate right by k

# Fixed-size sliding window — auto-evicts oldest
dq = deque(maxlen=k)

DS dict & Counter

Hash map backbone. defaultdict avoids KeyError on missing keys. Counter arithmetic is interview gold.

from collections import defaultdict, Counter

dd = defaultdict(list)
dd['a'].append(1)           # no KeyError

c = Counter("abracadabra")
c.most_common(3)            # top 3 by freq
c1 + c2                     # merge (sum counts)
c1 - c2                     # subtract (drops ≤0)
c1 & c2                     # intersection (min)
c1 | c2                     # union (max)

d.get(k, default)
d.setdefault(k, []).append(v)
{v: k for k, v in d.items()} # invert

DS heapq — min-heap

Python only has min-heap. Negate values for max-heap. Use tuple heaps (priority, item) for tie-breaking.

import heapq
h = []
heapq.heappush(h, x)         # O(log n)
heapq.heappop(h)              # O(log n) — min
heapq.heappushpop(h, x)      # push then pop, faster
heapq.heapify(lst)            # O(n) in-place
heapq.nlargest(k, arr)        # O(n log k)
heapq.nsmallest(k, arr)

# Max-heap: negate
heapq.heappush(h, -x)
max_val = -heapq.heappop(h)

# Tuple heap — sorted by first element
heapq.heappush(h, (priority, item))

DS set & frozenset

O(1) avg membership. frozenset is hashable — use it as a dict key or store it in a set (e.g. visited states in BFS).

s = {1, 2, 3}
s.add(4)           # O(1)
s.discard(x)       # no error if missing
x in s             # O(1)

s1 | s2            # union
s1 & s2            # intersection
s1 - s2            # difference
s1 ^ s2            # symmetric difference

# frozenset as hashable key
visited = set()
visited.add(frozenset([1, 2]))

DS SortedList (sortedcontainers)

Sorted order + O(log n) insert/delete. Not built-in but available on LeetCode and most OJs. Use when you need k-th smallest or range count queries.

from sortedcontainers import SortedList
sl = SortedList([3, 1, 4, 1, 5])
sl.add(2)              # O(log n)
sl.discard(1)          # O(log n)
sl.bisect_left(x)      # O(log n) index
sl[i]                  # O(log n)
sl[i:j]                # O(k) slice

# Count elements in range [a, b]
sl.bisect_right(b) - sl.bisect_left(a)

Stack-based structures

DS monotonic stack

Signal: "next/prev greater/smaller", daily temperatures, histogram area. Maintain invariant (increasing or decreasing) by popping on violation.

def next_greater(arr):
    n = len(arr)
    res = [-1] * n
    stack = []          # indices, values decreasing
    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            res[stack.pop()] = arr[i]
        stack.append(i)
    return res

# prev_smaller: iterate left, maintain increasing stack
# Largest rectangle in histogram → mono stack O(n)

DS min-stack

O(1) get_min alongside normal push/pop. Shadow stack tracks running minimum at each depth.

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val):
        self.stack.append(val)
        m = min(val, self.min_stack[-1]
                if self.min_stack else val)
        self.min_stack.append(m)

    def pop(self):
        self.stack.pop()
        self.min_stack.pop()

    def get_min(self):
        return self.min_stack[-1]

Foundational two-pointer & window

Pattern two pointers

Sorted array pair sums, container with most water, in-place reversal, palindrome check. Requires sorted input or specific structure.

def two_sum_sorted(arr, target):
    l, r = 0, len(arr) - 1
    while l < r:
        s = arr[l] + arr[r]
        if s == target:   return [l, r]
        elif s < target:  l += 1
        else:             r -= 1
    return []

Pattern sliding window

Variable window: shrink when constraint violated. Fixed window: advance l and r together. Use deque for sliding window max/min.

def longest_no_repeat(s):
    char_idx = {}
    l, res = 0, 0
    for r, c in enumerate(s):
        if c in char_idx and char_idx[c] >= l:
            l = char_idx[c] + 1
        char_idx[c] = r
        res = max(res, r - l + 1)
    return res

Search & range

Pattern binary search on answer

"Minimum X such that condition(X) is true." The search space is the answer domain, not the array index.

def binary_search_answer(lo, hi):
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid):
            hi = mid        # search left (minimize)
        else:
            lo = mid + 1
    return lo
# For maximize: flip condition — use lo = mid
# hi = lo + 1 for half-open interval variants

Pattern prefix sum & difference array

Range sum in O(1). Subarray sum = k via prefix + hash map. Difference array gives O(1) range updates.

from collections import defaultdict
from itertools import accumulate

def subarray_sum_k(nums, k):
    count, prefix = 0, 0
    seen = defaultdict(int)
    seen[0] = 1
    for n in nums:
        prefix += n
        count += seen[prefix - k]
        seen[prefix] += 1
    return count

# Range update in O(1) with difference array
diff = [0] * (n + 1)
diff[l] += val; diff[r + 1] -= val
result = list(accumulate(diff))

Linked list & cycle

Pattern fast & slow pointers

Floyd's cycle detection. Also: middle of list (slow stops at mid), happy number. When slow meets fast, reset slow to head to find cycle entry.

def detect_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow == fast:
            slow = head        # find entry point
            while slow != fast:
                slow = slow.next
                fast = fast.next
            return slow        # cycle start
    return None

Pattern backtracking template

Permutations, combinations, subsets, N-Queens, Sudoku. Always copy path on solution. Prune early — return when path can't lead to solution.

def backtrack(path, choices, result):
    if is_solution(path):
        result.append(path[:])   # copy!
        return
    for i, choice in enumerate(choices):
        if not is_valid(path, choice):
            continue
        path.append(choice)              # choose
        backtrack(path, choices[i+1:], result)
        path.pop()                       # unchoose

# Subsets: pass start index, not choices[i+1:]
# Permutations: pass remaining unused set

Graph primitives

Pattern Union-Find (DSU)

Connected components, cycle detection, Kruskal's MST. Path compression + union by rank gives near-O(1) per op.

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])
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False    # already connected
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]: self.rank[px] += 1
        return True

Pattern intervals

Sort by start. Merge when start ≤ prev_end. Meeting rooms II: min-heap of end times — pop if next start ≥ heap[0], else push.

def merge_intervals(intervals):
    intervals.sort()
    merged = [intervals[0]]
    for start, end in intervals[1:]:
        if start <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], end)
        else:
            merged.append([start, end])
    return merged

# Meeting rooms II
import heapq
def min_rooms(intervals):
    intervals.sort()
    heap = []
    for start, end in intervals:
        if heap and start >= heap[0]:
            heapq.heapreplace(heap, end)
        else:
            heapq.heappush(heap, end)
    return len(heap)

Tree traversals

Graph inorder — iterative

Safe for deep trees — no recursion limit risk. Same pattern adapts to preorder (process before pushing left) and postorder.

def inorder(root):
    res, stack = [], []
    cur = root
    while cur or stack:
        while cur:
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()
        res.append(cur.val)
        cur = cur.right
    return res

Graph level-order BFS

Snapshot len(q) at the start of each level — this is the "process one level at a time" trick that makes level separation clean.

from collections import deque

def level_order(root):
    if not root: return []
    q = deque([root])
    res = []
    while q:
        level = []
        for _ in range(len(q)):      # snapshot this level
            node = q.popleft()
            level.append(node.val)
            if node.left:  q.append(node.left)
            if node.right: q.append(node.right)
        res.append(level)
    return res

Graph traversal

Graph BFS — shortest path

Unweighted shortest path. Always mark visited before enqueuing, not after dequeuing — avoids re-adding the same node.

from collections import defaultdict, deque

def bfs(start, end, graph):
    q = deque([(start, 0)])
    visited = {start}
    while q:
        node, dist = q.popleft()
        if node == end: return dist
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)    # mark before enqueue
                q.append((nei, dist + 1))
    return -1

Graph DFS — iterative

Convert recursive DFS to iterative to avoid hitting Python's 1000 recursion limit on deep graphs.

def dfs(start, graph):
    stack = [start]
    visited = {start}
    while stack:
        node = stack.pop()
        for nei in graph[node]:
            if nei not in visited:
                visited.add(nei)
                stack.append(nei)

# Build adjacency list
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)   # undirected

Shortest paths

Graph Dijkstra

Weighted graph, non-negative edges. Stale entry check (if d > dist[u]: continue) is essential — without it, you reprocess old heap entries.

import heapq
from collections import defaultdict

def dijkstra(n, edges, src):
    graph = defaultdict(list)
    for u, v, w in edges:
        graph[u].append((w, v))
    dist = [float('inf')] * n
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue       # stale — skip
        for w, v in graph[u]:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                heapq.heappush(heap, (dist[v], v))
    return dist

Graph Bellman-Ford

Handles negative edges. Relax all edges n-1 times. An n-th relaxation that still updates → negative cycle exists.

def bellman_ford(n, edges, src):
    dist = [float('inf')] * n
    dist[src] = 0
    for _ in range(n - 1):
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    # n-th pass: negative cycle detection
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None   # negative cycle
    return dist

Ordering & connectivity

Graph topological sort (Kahn's)

BFS-based topo sort. If output length < n, a cycle exists. Course schedule, build order, task dependency problems.

def topo_sort(n, prerequisites):
    graph = defaultdict(list)
    indegree = [0] * n
    for u, v in prerequisites:
        graph[v].append(u)
        indegree[u] += 1
    q = deque(i for i in range(n) if indegree[i] == 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) == n else []  # [] = cycle

Graph Trie

Prefix tree for string search, autocomplete, word dictionary. starts_with is O(len(prefix)) — much faster than a hash set for prefix queries.

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for c in word:
            node = node.children.setdefault(c, TrieNode())
        node.is_end = True

    def search(self, word):
        node = self.root
        for c in word:
            if c not in node.children: return False
            node = node.children[c]
        return node.is_end

    def starts_with(self, prefix):
        node = self.root
        for c in prefix:
            if c not in node.children: return False
            node = node.children[c]
        return True

Approach checklist

1. identify state 2. define dp[i] in English 3. write recurrence 4. base case + iteration order 5. space optimize?

Classic patterns

DP 1D — Fibonacci family

Climbing stairs, min cost climbing, house robber. Reduce to two variables once you recognise only adjacent states matter.

# dp[i] = dp[i-1] + dp[i-2]
prev2, prev1 = 1, 1
for i in range(2, n + 1):
    prev2, prev1 = prev1, prev1 + prev2

# House robber variant: max(dp[i-1], dp[i-2] + val)

DP LIS — O(n log n)

Patience sorting. sub is not the actual LIS — only its length is correct. Use parent tracking to reconstruct the sequence.

import bisect

def lis(nums):
    sub = []
    for x in nums:
        pos = bisect.bisect_left(sub, x)
        if pos == len(sub):
            sub.append(x)
        else:
            sub[pos] = x     # replace to keep sub minimal
    return len(sub)

DP 0/1 knapsack

Reverse inner loop — ensures each item is used at most once. Forward loop = unbounded knapsack (items reusable).

def knapsack(weights, values, cap):
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):  # reverse = each item once
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]
# forward range(w, cap+1) → unbounded (coin change)

DP LCS — 2D

Longest Common Subsequence. Basis for edit distance, diff algorithms. Space-optimizable to O(min(m,n)) using two rows.

def lcs(s, t):
    m, n = len(s), len(t)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s[i-1] == t[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[m][n]

DP interval DP

Matrix chain multiplication, burst balloons, stone merge. Always iterate by increasing window length, split at every k in [i, j).

dp = [[0] * n for _ in range(n)]
for length in range(2, n + 1):
    for i in range(n - length + 1):
        j = i + length - 1
        dp[i][j] = float('inf')
        for k in range(i, j):         # split point
            dp[i][j] = min(
                dp[i][j],
                dp[i][k] + dp[k+1][j] + cost(i, k, j)
            )

DP bitmask DP

TSP, assignment problems, covering all subsets. Feasible up to n ≈ 20–22. State: which items visited + current position.

def tsp(dist, n):
    full = (1 << n) - 1
    dp = [[float('inf')] * n for _ in range(1 << n)]
    dp[1][0] = 0
    for mask in range(1 << n):
        for u in range(n):
            if not (mask >> u & 1): continue
            for v in range(n):
                if mask >> v & 1: continue
                nmask = mask | (1 << v)
                dp[nmask][v] = min(dp[nmask][v],
                                   dp[mask][u] + dist[u][v])
    return min(dp[full][i] + dist[i][0] for i in range(1, n))

Memoization

DP @cache / @lru_cache

One decorator turns recursion into top-down DP. Args must be hashable — convert lists to tuples. Clear between test cases in competitions.

from functools import cache, lru_cache

@cache                        # Python 3.9+ — unbounded
def fib(n):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

fib.cache_clear()             # reset between test cases
fib.cache_info()              # hits / misses / currsize

# Args must be hashable — wrap mutable state
@cache
def solve(mask: int, pos: int) -> int: ...

# Convert list to tuple when needed
dp(tuple(arr), target)

DP top-down vs bottom-up

Both are equivalent. Top-down is easier to write; bottom-up avoids recursion overhead and is easier to space-optimize. Prefer bottom-up for space reduction.

# Top-down: let @cache handle it
@cache
def dp(i, j): ...

# Bottom-up: explicit iteration order
# Space optimize: if dp[i] only needs dp[i-1]
# → replace 2D table with two 1D arrays

prev = [0] * (n + 1)
curr = [0] * (n + 1)
for i in range(1, m + 1):
    for j in range(1, n + 1):
        curr[j] = ...
    prev, curr = curr, [0] * (n + 1)

itertools essentials

Trick itertools for DSA

from itertools import (
    accumulate,                    # prefix sums, running max
    combinations,                  # C(n,r) no repeat
    combinations_with_replacement,
    permutations,                  # P(n,r)
    product,                       # cartesian product
    chain,                         # flatten iterables
    pairwise,                      # adjacent pairs (3.10+)
)

list(accumulate(arr))              # prefix sums
list(accumulate(arr, max))         # running max
list(accumulate(arr, lambda a,b: a*b))  # prefix product

list(combinations(arr, k))         # all size-k subsets
list(product([-1,0,1], repeat=2))  # all (dr,dc) grid dirs
dirs = [(0,1),(0,-1),(1,0),(-1,0)] # 4-directional

Trick sorting power moves

# Multi-key sort
arr.sort(key=lambda x: (x[1], -x[0]))

# Strings by length then lex
words.sort(key=lambda w: (len(w), w))

# Custom comparator — "largest number" problem
from functools import cmp_to_key
def cmp(a, b):
    if a + b > b + a: return -1  # a before b
    return 1
strs.sort(key=cmp_to_key(cmp))

# Coordinate compression
sv = sorted(set(arr))
rank = {v: i for i, v in enumerate(sv)}
compressed = [rank[x] for x in arr]

Array / matrix tricks

Trick matrix operations

# Transpose
transposed = [list(r) for r in zip(*matrix)]

# Rotate 90° clockwise
rotated = [list(r) for r in zip(*matrix[::-1])]

# Rotate 90° counter-clockwise
rotated = [list(r) for r in zip(*matrix)][::-1]

# Flatten 2D
flat = [x for row in matrix for x in row]

# Deep copy 2D (faster than copy.deepcopy)
copy = [row[:] for row in matrix]

Trick string tricks

# Anagram check
Counter(s) == Counter(t)
sorted(s) == sorted(t)    # O(n log n) — slower

# All char frequencies (lowercase only)
freq = [0] * 26
for c in s:
    freq[ord(c) - ord('a')] += 1

# Palindrome
s == s[::-1]

# All substrings
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        sub = s[i:j]

# Split and rejoin
' '.join(reversed(s.split()))

Number theory

Trick math essentials

import math

math.gcd(a, b)            # Euclidean GCD
math.lcm(a, b)            # Python 3.9+
pow(base, exp, mod)       # fast modular exp O(log n)

# Modular inverse (prime modulus only)
inv = pow(a, MOD - 2, MOD)   # Fermat's little theorem

# Sieve of Eratosthenes
def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if is_prime[i]:
            for j in range(i*i, n+1, i):
                is_prime[j] = False
    return [i for i, p in enumerate(is_prime) if p]

Trick bit manipulation

bin(n).count('1')     # popcount
n.bit_count()         # Python 3.10+
n & (n - 1)           # clear lowest set bit
n & (-n)              # isolate lowest set bit
n ^ n                 # = 0 (XOR with itself)
a ^ b ^ a             # = b (XOR trick for missing number)

# Check k-th bit
n >> k & 1

# Set k-th bit
n | (1 << k)

# Enumerate all subsets of a bitmask
sub = mask
while sub:
    process(sub)
    sub = (sub - 1) & mask

Competition I/O & gotchas

Trick fast I/O

import sys
input = sys.stdin.readline    # ~5x faster

# Read all at once
data = sys.stdin.read().split()
idx = 0
def rd():
    global idx; idx += 1; return data[idx - 1]
def ri(): return int(rd())

# Fast output
out = []
out.append(str(result))
sys.stdout.write('\n'.join(out) + '\n')

# Multi-test template
T = int(input())
for _ in range(T):
    n = int(input())
    arr = list(map(int, input().split()))

Trick Python-specific gotchas in DSA

These trip up C++/Java devs writing Python in contests.

# Floor division — rounds toward -inf (not zero)
7  // 2   # =  3
-7 // 2   # = -4  (not -3 like C++)

# Modulo follows divisor sign
-7 % 3    # = 2   (positive — Python), not -1

# No integer overflow — Python has BigInt!
# float('inf') works as infinity sentinel

# Recursion limit
import sys
sys.setrecursionlimit(200_000)

# Mutable default — classic bug
def f(arr=[]):   # WRONG — shared across calls
def f(arr=None):
    arr = arr or []   # correct

Built-ins & algorithms

Python built-in complexity

list append / pop (end)	O(1) amort
list insert / del at i	O(n)
list search (in)	O(n)
dict / set get, set, del	O(1) avg
deque append / pop (both)	O(1)
heapq push / pop	O(log n)
heapify	O(n)
sorted() / .sort()	O(n log n)
bisect_left / right	O(log n)
SortedList add / discard	O(log n)

Algorithm reference

Binary search	O(log n)
BFS / DFS	O(V + E)
Dijkstra (min-heap)	O((V+E) log V)
Bellman-Ford	O(V · E)
Floyd-Warshall	O(V³)
Kruskal's MST	O(E log E)
Topological sort (Kahn)	O(V + E)
Union-Find (path compress)	O(α(n)) ≈ O(1)
LIS (patience sorting)	O(n log n)
Knapsack 0/1	O(n × W)

Constraints → approach heuristic

Python is ~10–50x slower than C++. Assume ~10⁷ safe ops/sec for CPython, ~10⁸ for PyPy.

n ≤ 10	O(n!) — backtrack / perms
n ≤ 20–25	O(2ⁿ) — bitmask DP
n ≤ 100	O(n³) — Floyd-Warshall, interval DP
n ≤ 1 000	O(n²) — 2D DP, brute force
n ≤ 10⁵	O(n log n) — sort, heap, seg tree
n ≤ 10⁶	O(n) — linear scan, hash map
n ≤ 10⁹	O(log n) or O(√n)

Space & recursion notes

Default recursion limit	1 000
Recommended limit	sys.setrecursionlimit(2*10**5)
2D DP → rolling 1D	O(n²) → O(n)
DFS stack vs recursion	same O(depth)
BFS space	O(w) — max width

For any DFS with depth > 1 000, convert to iterative or call sys.setrecursionlimit explicitly.