DSA Patterns

Big O Cheat Sheet

Common structure costs: array access O(1), array insert/delete at front O(n), hash map get/set O(1) average, balanced BST get/set O(log n), heap push/pop O(log n).

Two Pointer

Two indices scan from opposite ends (or same direction at different speeds) to avoid an O(n²) nested loop — typically on a sorted array.

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1
    while left < right:
        s = nums[left] + nums[right]
        if s == target:
            return [left, right]
        elif s < target:
            left += 1
        else:
            right -= 1
    return []

Use when: sorted input, pair/triplet sum problems, reversing/palindrome checks, removing duplicates in-place.

Sliding Window

A window [left, right] expands and contracts over a sequence to track a running property (sum, count, distinct chars) in O(n) instead of recomputing per window.

def longest_unique_substring(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Use when: “longest/shortest substring/subarray satisfying X”, contiguous subarray sums, fixed or variable window size.

Fast And Slow Pointers

Two pointers move through a linked structure at different speeds (Floyd’s cycle detection) to find cycles, midpoints, or the nth-from-end node without extra memory.

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

def find_middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow  # middle node

Binary Search

Halve the search space each step on sorted (or monotonic-condition) data — O(log n).

def binary_search(nums, target):
    lo, hi = 0, len(nums) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

Beyond plain search: “binary search on the answer” applies the same halving to any monotonic predicate (e.g. minimum capacity that satisfies a constraint), not just array lookups.

Depth And Breadth First Search

DFS explores as deep as possible before backtracking (stack / recursion); BFS explores level by level (queue) — BFS gives shortest path on unweighted graphs.

def dfs(graph, start, visited=None):
    visited = visited or set()
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

from collections import deque
def bfs(graph, start):
    visited, queue = {start}, deque([start])
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return order

Use DFS for: connectivity, cycle detection, topological sort, exhaustive path exploration. Use BFS for: shortest path (unweighted), level-order traversal, “minimum steps” problems.

Backtracking

Build a solution incrementally, abandon (“backtrack”) as soon as a partial candidate can’t lead to a valid one. Used for permutations, combinations, subsets, constraint satisfaction (N-Queens, Sudoku).

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()  # undo — the backtrack step
    backtrack(0, [])
    return result

Template: choose → explore → un-choose. Prune early (return/continue) when a partial path already violates a constraint.

Dynamic Programming

Break a problem into overlapping subproblems, cache results (memoization, top-down) or build a table bottom-up to avoid recomputation.

# top-down with memoization
from functools import lru_cache
@lru_cache(maxsize=None)
def climb_stairs(n):
    if n <= 2:
        return n
    return climb_stairs(n - 1) + climb_stairs(n - 2)

# bottom-up with a table
def coin_change(coins, amount):
    dp = [0] + [float("inf")] * amount
    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] != float("inf") else -1

Recognize DP when: the problem asks for an optimum (min/max/count of ways) and has overlapping subproblems + optimal substructure (the optimal solution is built from optimal solutions to subproblems).

Heaps And Top K

A heap (priority queue) gives O(log n) insert and O(1) peek at the min/max — ideal for “top K” / “K closest” / streaming median problems without a full sort.

import heapq

def top_k_frequent(nums, k):
    from collections import Counter
    counts = Counter(nums)
    return heapq.nlargest(k, counts.keys(), key=counts.get)

# manual min-heap of size k for "k largest"
def k_largest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap  # smallest of the k largest is heap[0]

Python’s heapq is a min-heap only — negate values to simulate a max-heap.

Union Find

Disjoint Set Union tracks a partition of elements into groups with near-O(1) find/union (path compression + union by rank) — used for connectivity, cycle detection in undirected graphs, and Kruskal’s MST.

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 True

Intervals

Sort by start time, then merge or sweep — turns most interval problems into a single O(n log n) pass.

def merge_intervals(intervals):
    intervals.sort(key=lambda iv: iv[0])
    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

Common variants: merge overlapping intervals, insert a new interval, count meeting rooms needed (min heap of end times), find free/gaps between intervals.

Prefix Sums

Precompute cumulative sums so any range-sum query answers in O(1) after an O(n) build — trades memory for speed on repeated range queries.

def build_prefix(nums):
    prefix = [0] * (len(nums) + 1)
    for i, n in enumerate(nums):
        prefix[i + 1] = prefix[i] + n
    return prefix

def range_sum(prefix, left, right):  # inclusive [left, right]
    return prefix[right + 1] - prefix[left]

2D variant (prefix sum over a matrix) extends the same idea for rectangle-sum queries in O(1) after O(rows × cols) build.