Coding Patterns

Sliding window maintains a contiguous window over a sequence, expanding or shrinking it to satisfy a constraint. It is most applicable when you need aggregates over all subarrays of fixed size k, or the shortest/longest subarray meeting a condition. Rather than recomputing from scratch each step, you add the incoming element and remove the outgoing one, reducing O(n·k) brute-force to O(n). Common problems: maximum sum subarray of size k, longest substring without repeating characters, minimum window substring.

def max_sum_k(arr, k):
    s = sum(arr[:k])
    best = s
    for i in range(len(arr) - k):
        s += arr[i + k] - arr[i]
        best = max(best, s)
    return best

Two-pointer uses two indices moving through a sequence to eliminate nested iteration. In the converging variant, left starts at 0 and right at n-1 and they move toward each other—ideal for sorted-array problems like Two Sum or Container With Most Water. In the parallel variant, both pointers move in the same direction at potentially different speeds, useful for removing duplicates in-place or merging sorted arrays. Both variants achieve O(n) time instead of O(n²) brute force and use O(1) extra space.

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 -1

Fast/slow pointers (Floyd's tortoise and hare) use two pointers advancing at different speeds through a linked structure. The slow pointer moves one step at a time while the fast pointer moves two. If a cycle exists, the fast pointer will eventually lap the slow pointer and they will meet. After meeting, resetting one pointer to the head and advancing both one step at a time finds the cycle start. Applications include cycle detection, finding cycle entry, finding the middle of a linked list, and detecting happy numbers.

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

The Merge Intervals pattern is used when you have a list of intervals and need to combine overlapping ones. Sort by start time first, then iterate: if the current interval's start is less than or equal to the last merged interval's end, merge them by updating the end to the maximum of both ends. Otherwise, add the current interval as a new entry. This runs in O(n log n) due to sorting and O(n) for the merge pass. Variants include inserting a new interval and finding intersections.

def merge(intervals):
    intervals.sort(key=lambda x: x[0])
    merged = [intervals[0]]
    for s, e in intervals[1:]:
        if s <= merged[-1][1]:
            merged[-1][1] = max(merged[-1][1], e)
        else:
            merged.append([s, e])
    return merged

Binary search on the answer space (also called parametric search) applies when the answer is a numeric value within a known range and you can verify in O(n) or O(n log n) whether a candidate answer is feasible. You binary search over the answer range rather than an array index. It converts many optimization problems from O(n²) to O(n log n). Classic examples: Koko Eating Bananas (minimum eating speed), Capacity to Ship Packages, minimum days to make m bouquets.

def min_speed(piles, h):
    def feasible(speed):
        return sum(-(-p // speed) for p in piles) <= h
    lo, hi = 1, max(piles)
    while lo < hi:
        mid = (lo + hi) // 2
        if feasible(mid): hi = mid
        else: lo = mid + 1
    return lo

A monotonic stack is a stack that maintains elements in strictly increasing or strictly decreasing order. When processing each element, you pop elements that violate the monotonic property, which gives you the nearest greater or smaller element for each popped item in O(1) amortized. Total time is O(n) because each element is pushed and popped at most once. Classic problems: Next Greater Element, Daily Temperatures, Largest Rectangle in Histogram, and Trapping Rain Water using left/right boundary precomputation.

def next_greater(arr):
    n = len(arr)
    res = [-1] * n
    stack = []
    for i, val in enumerate(arr):
        while stack and arr[stack[-1]] < val:
            res[stack.pop()] = val
        stack.append(i)
    return res

Prefer BFS when you need the shortest path in an unweighted graph, because BFS explores all vertices at distance d before exploring vertices at distance d+1, guaranteeing the first time a node is reached it is via the shortest path. BFS is also better for level-order tree traversal and multi-source problems. DFS is preferred for cycle detection, topological sort, finding all paths, connected components in sparse graphs, and problems requiring backtracking. BFS uses O(w) space (w = max width) while DFS uses O(h) space (h = max depth).

from collections import deque
def bfs_shortest(graph, src, dst):
    q = deque([(src, 0)])
    visited = {src}
    while q:
        node, dist = q.popleft()
        if node == dst: return dist
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)
                q.append((nb, dist + 1))
    return -1

Backtracking explores all candidate solutions by building them incrementally and abandoning (pruning) partial candidates that cannot yield valid solutions. The three key decisions are: (1) Choice — what options can be added at the current step; (2) Constraint — what condition must hold for a partial solution to remain viable; (3) Goal — when is the solution complete. The template is: if goal reached, record result; for each valid choice, make choice, recurse, undo choice. This is used in permutations, subsets, N-Queens, Sudoku, and word search.

def permutations(nums):
    res, path = [], []
    used = [False] * len(nums)
    def bt():
        if len(path) == len(nums):
            res.append(path[:]); return
        for i, n in enumerate(nums):
            if not used[i]:
                used[i] = True; path.append(n)
                bt()
                path.pop(); used[i] = False
    bt(); return res

Prefix sum precomputes a cumulative array P where P[i] = arr[0] + arr[1] + ... + arr[i-1]. After O(n) preprocessing, any range sum query sum(arr[l..r]) is answered in O(1) as P[r+1] - P[l]. This avoids recomputing sums for overlapping ranges. The 2D variant extends to matrices, enabling O(1) rectangle sum queries after O(m·n) preprocessing. Prefix sums are used in subarray sum problems, count of subarrays with given sum (using a hashmap), and image processing.

def build_prefix(arr):
    pre = [0] * (len(arr) + 1)
    for i, v in enumerate(arr):
        pre[i+1] = pre[i] + v
    return pre

def range_sum(pre, l, r):
    return pre[r+1] - pre[l]

The Top-K elements pattern uses a min-heap of size k to find the k largest elements, or a max-heap of size k to find the k smallest. For finding k largest: iterate all n elements, pushing each onto the min-heap; if heap size exceeds k, pop the minimum. The heap maintains the k largest seen so far. Final complexity is O(n log k), which is better than sorting at O(n log n) when k is much smaller than n. Python's heapq module provides a min-heap; negate values to simulate a max-heap.

import heapq
def top_k_largest(nums, k):
    heap = []
    for n in nums:
        heapq.heappush(heap, n)
        if len(heap) > k:
            heapq.heappop(heap)
    return list(heap)

K-way merge combines k sorted lists into one sorted list. A naive approach of merging one at a time costs O(n·k). The efficient approach initializes a min-heap with the first element from each of the k lists. Each iteration extracts the minimum, adds it to the result, and pushes the next element from the same list. Each element is pushed and popped exactly once, giving O(n log k) total time. Applications include merging k sorted arrays, finding the smallest range covering k lists, and external sort.

import heapq
def k_merge(lists):
    heap, res = [], []
    for i, lst in enumerate(lists):
        if lst: heapq.heappush(heap, (lst[0], i, 0))
    while heap:
        val, i, j = heapq.heappop(heap)
        res.append(val)
        if j + 1 < len(lists[i]):
            heapq.heappush(heap, (lists[i][j+1], i, j+1))
    return res

Cyclic sort exploits the property that when values are in the range 1 to n (or 0 to n-1), each value v belongs at index v-1. It places each element at its correct index by swapping, iterating until all elements are in place. Time is O(n) and space is O(1), beating any comparison-based sort. It is specifically useful for problems that ask you to find missing numbers, duplicates, or the smallest missing positive in arrays whose values are constrained to a known integer range.

def find_missing(nums):
    i = 0
    while i < len(nums):
        j = nums[i] - 1
        if 0 <= j < len(nums) and nums[i] != nums[j]:
            nums[i], nums[j] = nums[j], nums[i]
        else:
            i += 1
    return [i+1 for i, v in enumerate(nums) if v != i+1]

In-place linked list reversal uses three pointers: prev (initially None), curr (initially head), and next_node. At each step: save curr.next in next_node, redirect curr.next to prev, advance prev to curr, advance curr to next_node. Repeat until curr is None; then prev is the new head. This completes in O(n) time and O(1) space. The recursive variant uses the call stack (O(n) space). Variants include reversing a sublist [left, right] by locating the boundary nodes before applying the reversal.

def reverse_list(head):
    prev, curr = None, head
    while curr:
        nxt = curr.next
        curr.next = prev
        prev = curr
        curr = nxt
    return prev

Two heaps partitions a stream of numbers into a lower half (max-heap) and upper half (min-heap), keeping them balanced so their sizes differ by at most one. The median is the top of the larger heap or the average of both tops when sizes are equal. Adding a number: push to max-heap, then rebalance by moving the max-heap top to the min-heap if the max-heap top exceeds the min-heap top. Rebalance sizes if they diverge by more than one. Each insertion is O(log n). This pattern also solves task scheduler and sliding window median variants.

import heapq
class MedianFinder:
    def __init__(self):
        self.lo, self.hi = [], []  # max-heap (negated), min-heap
    def add(self, num):
        heapq.heappush(self.lo, -num)
        heapq.heappush(self.hi, -heapq.heappop(self.lo))
        if len(self.hi) > len(self.lo):
            heapq.heappush(self.lo, -heapq.heappop(self.hi))
    def median(self):
        if len(self.lo) > len(self.hi): return -self.lo[0]
        return (-self.lo[0] + self.hi[0]) / 2

The subsets pattern generates all 2^n subsets of a set. The iterative BFS approach starts with an empty set and for each new element, duplicates every existing subset and appends the element to each duplicate. The backtracking approach builds subsets by deciding at each index whether to include or exclude the current element, recording the path at each node of the decision tree. For subsets with duplicates, sort the array and skip consecutive duplicate choices at the same recursion depth. All approaches are O(2^n × n) time since each subset can be up to n elements long.

def subsets(nums):
    res = [[]]
    for n in nums:
        res += [sub + [n] for sub in res]
    return res

A rotated sorted array has one sorted half on either side of the pivot. At each binary search step, determine which half is sorted: if arr[mid] >= arr[lo], the left half is sorted; otherwise the right half is sorted. Then check whether the target falls within the sorted half. If yes, narrow the search to that half; otherwise search the other half. This finds the target in O(log n). The key insight is that at least one half is always sorted after any rotation, enabling standard binary search logic on that half.

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

XOR has two key properties: x XOR x = 0 (a number XORed with itself is zero) and x XOR 0 = x (identity). XORing all elements together causes every element that appears twice to cancel to zero, leaving only the element that appears once. This runs in O(n) time and O(1) space, far superior to hash sets which need O(n) space. The same XOR technique finds two missing numbers, detects bit differences, and solves Single Number II (appearing three times) with bit-count mod 3.

from functools import reduce
def single_number(nums):
    return reduce(lambda a, b: a ^ b, nums)

Topological sort produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge u→v, u comes before v. It is used for task scheduling, build systems, and course prerequisites. Two standard implementations exist: Kahn's algorithm (BFS) repeatedly removes nodes with in-degree zero, adding them to the result and decrementing neighbors' in-degrees. DFS-based sort runs DFS and appends each finished node to a stack, then reverses it. Both run in O(V + E). If any cycle exists, not all nodes will be processed, enabling cycle detection.

from collections import deque
def topo_sort(n, edges):
    indeg = [0]*n
    g = [[] for _ in range(n)]
    for u, v in edges:
        g[u].append(v); indeg[v] += 1
    q = deque(i for i in range(n) if indeg[i]==0)
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in g[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order)==n else []

Union-Find maintains a forest where each tree represents a connected component. Find(x) returns the root of x's tree; Union(x, y) merges the trees containing x and y. Two optimizations make it nearly O(1) amortized: path compression (make every node on the path to root point directly to the root) and union by rank or size (attach the smaller tree under the larger root). Combined, they achieve O(α(n)) per operation, where α is the inverse Ackermann function, practically constant for all realistic n. Used for Kruskal's MST, detecting cycles, and dynamic connectivity.

class DSU:
    def __init__(self, n):
        self.p = list(range(n))
        self.rank = [0]*n
    def find(self, x):
        if self.p[x] != x:
            self.p[x] = self.find(self.p[x])
        return self.p[x]
    def union(self, x, y):
        px, py = self.find(x), self.find(y)
        if px == py: return False
        if self.rank[px] < self.rank[py]: px, py = py, px
        self.p[py] = px
        if self.rank[px]==self.rank[py]: self.rank[px]+=1
        return True

Multi-source BFS initializes the queue with multiple starting nodes simultaneously rather than one. This effectively computes the shortest distance from any source to every other node in a single BFS pass, equivalent to adding a virtual super-source connected to all real sources. It is O(V + E) just like single-source BFS. Classic uses include the 01 Matrix problem (distance to nearest zero), Rotting Oranges (minimum minutes until all oranges rot), and walls-and-gates. The key insight is that all sources are at distance 0, so BFS naturally fans out in parallel from all of them.

from collections import deque
def nearest_zero(matrix):
    m, n = len(matrix), len(matrix[0])
    dist = [[float('inf')]*n for _ in range(m)]
    q = deque()
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                dist[i][j] = 0; q.append((i,j))
    while q:
        r, c = q.popleft()
        for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
            nr, nc = r+dr, c+dc
            if 0<=nr<m and 0<=nc<n and dist[nr][nc]>dist[r][c]+1:
                dist[nr][nc]=dist[r][c]+1; q.append((nr,nc))
    return dist

Divide and conquer splits a problem into smaller independent subproblems, solves each recursively, and combines results. Merge sort divides an array at the midpoint, recursively sorts both halves (divide), then merges the two sorted halves in O(n) (conquer). The recurrence T(n) = 2T(n/2) + O(n) solves by Master Theorem to O(n log n). The merge step is the key: use two pointers on each half, always appending the smaller element. This guarantees stable sort, predictable O(n log n) worst case, and is the foundation for counting inversions and external sorting.

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    L, R = merge_sort(arr[:mid]), merge_sort(arr[mid:])
    res, i, j = [], 0, 0
    while i < len(L) and j < len(R):
        if L[i] <= R[j]: res.append(L[i]); i+=1
        else: res.append(R[j]); j+=1
    return res + L[i:] + R[j:]

The interval scheduling maximization problem asks for the maximum number of non-overlapping intervals. The greedy algorithm sorts intervals by end time and greedily selects each interval that starts after the last selected interval ends. Selecting the interval with the earliest end time leaves the most room for future intervals—no other choice of first interval can lead to strictly more selections. This exchange argument proves optimality. The algorithm runs in O(n log n) for sorting plus O(n) for selection. Variants include minimum number of platforms needed and interval coloring.

def max_non_overlap(intervals):
    intervals.sort(key=lambda x: x[1])
    count, end = 0, float('-inf')
    for s, e in intervals:
        if s >= end:
            count += 1
            end = e
    return count

In 0/1 Knapsack each item is either taken wholly or not—you cannot take a fraction—so greedy fails. Dynamic programming is required: dp[j] = max value with capacity j. Iterate items; for each, update dp in reverse (to avoid using the same item twice): dp[j] = max(dp[j], dp[j-w]+v). Time is O(n·W). Fractional Knapsack allows taking fractions, so greedy works: sort by value/weight ratio and take greedily. O(n log n). The critical difference is that greedy fails for 0/1 because a high-ratio item might not fill capacity efficiently, leaving wasted space.

def knapsack_01(weights, values, W):
    dp = [0] * (W + 1)
    for w, v in zip(weights, values):
        for j in range(W, w-1, -1):
            dp[j] = max(dp[j], dp[j-w] + v)
    return dp[W]

LCS finds the longest subsequence common to two strings without requiring contiguity. Define dp[i][j] as LCS length for s1[:i] and s2[:j]. If s1[i-1] == s2[j-1], dp[i][j] = dp[i-1][j-1] + 1; otherwise dp[i][j] = max(dp[i-1][j], dp[i][j-1]). Fill the (m+1) × (n+1) table bottom-up in O(m·n) time and space, reducible to O(min(m,n)) space using two rows. LCS is foundational: edit distance, shortest common supersequence, and diff tools all build on it.

def lcs(s1, s2):
    m, n = len(s1), len(s2)
    dp = [[0]*(n+1) for _ in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if s1[i-1]==s2[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]

The Dutch National Flag algorithm, by Dijkstra, partitions an array containing three distinct values (0, 1, 2) into three sections in O(n) time and O(1) space. Three pointers are used: lo (boundary of 0s), mid (current element), hi (boundary of 2s). If arr[mid] is 0, swap with arr[lo] and increment both; if 2, swap with arr[hi] and decrement hi only (mid stays to recheck); if 1, just increment mid. This solves the Sort Colors problem and is the basis for three-way quicksort partitioning, which efficiently handles arrays with many duplicate keys.

def sort_colors(nums):
    lo, mid, hi = 0, 0, len(nums)-1
    while mid <= hi:
        if nums[mid]==0:
            nums[lo],nums[mid]=nums[mid],nums[lo]
            lo+=1; mid+=1
        elif nums[mid]==2:
            nums[mid],nums[hi]=nums[hi],nums[mid]
            hi-=1
        else:
            mid+=1

Reservoir sampling selects k items uniformly at random from a stream of unknown or very large size n without storing all n items. Algorithm R: fill a reservoir with the first k items. For the i-th item (i > k), generate a random integer j in [1, i]. If j ≤ k, replace reservoir[j] with the i-th item. This guarantees each item has exactly k/n probability of being selected. Space is O(k) regardless of stream length. It is essential when the dataset is too large to fit in memory or when processing live data streams where n is not known in advance.

import random
def reservoir_sample(stream, k):
    res = []
    for i, item in enumerate(stream):
        if i < k:
            res.append(item)
        else:
            j = random.randint(0, i)
            if j < k:
                res[j] = item
    return res

Use a variable-size sliding window with two frequency maps: one for the target string t, one for the current window. Expand the right pointer, adding characters to the window map and tracking how many unique characters are fully satisfied (have count ≥ required). Once all characters are satisfied, shrink from the left to minimize window size while maintaining the constraint, recording the minimum. Contract until the constraint breaks, then expand again. Total time is O(|s| + |t|) since each character is added and removed at most once. Space is O(|t|) for the frequency map.

from collections import Counter
def min_window(s, t):
    need = Counter(t)
    have, total = 0, len(need)
    l, res, rlen = 0, "", float('inf')
    window = {}
    for r, c in enumerate(s):
        window[c] = window.get(c,0)+1
        if c in need and window[c]==need[c]: have+=1
        while have==total:
            if r-l+1 < rlen: rlen=r-l+1; res=s[l:r+1]
            window[s[l]]-=1
            if s[l] in need and window[s[l]]<need[s[l]]: have-=1
            l+=1
    return res

Trapping Rain Water asks how much water a histogram can hold. Water at position i is min(max_left[i], max_right[i]) - height[i]. The naive approach precomputes left-max and right-max arrays in O(n) time and space. The O(1) space two-pointer approach: maintain left_max and right_max, advance the pointer with the smaller max because that side determines the water. If left_max < right_max, water at left = left_max - height[left]; otherwise water at right = right_max - height[right]. Both approaches run in O(n) time; the two-pointer uses O(1) space.

def trap(height):
    l, r = 0, len(height)-1
    lmax = rmax = water = 0
    while l < r:
        if height[l] < height[r]:
            if height[l] >= lmax: lmax = height[l]
            else: water += lmax - height[l]
            l += 1
        else:
            if height[r] >= rmax: rmax = height[r]
            else: water += rmax - height[r]
            r -= 1
    return water

Sliding window maximum finds the maximum in every contiguous subarray of size k. A naive approach recomputes the max in each window, giving O(n·k). The optimal solution uses a monotonic deque (double-ended queue) that stores indices in decreasing order of their values. For each new element: remove from the back any indices with values less than the current value (they can never be the max); remove from the front indices outside the current window. The front always holds the current window's maximum. Each index is added and removed at most once, giving O(n) total time.

from collections import deque
def max_sliding_window(nums, k):
    dq, res = deque(), []
    for i, n in enumerate(nums):
        while dq and nums[dq[-1]] < n: dq.pop()
        dq.append(i)
        if dq[0] == i - k: dq.popleft()
        if i >= k - 1: res.append(nums[dq[0]])
    return res

Word search explores a 2D grid to find if a word exists as a sequence of adjacent cells (horizontally or vertically) where each cell is used at most once. The backtracking approach: for each cell matching word[0], start a DFS. At each step, mark the current cell as visited (e.g., temporarily replace with '#'), recurse in all four directions for the next character, then restore the cell. If all characters match, return True. Pruning: return False immediately if out of bounds, already visited, or character mismatch. Worst-case time is O(m·n·4^L) where L is word length.

def exist(board, word):
    m, n = len(board), len(board[0])
    def dfs(r, c, i):
        if i == len(word): return True
        if r<0 or r>=m or c<0 or c>=n or board[r][c]!=word[i]: return False
        tmp, board[r][c] = board[r][c], '#'
        found = any(dfs(r+dr,c+dc,i+1) for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)])
        board[r][c] = tmp
        return found
    return any(dfs(r,c,0) for r in range(m) for c in range(n))

A graph is bipartite if its vertices can be split into two disjoint sets such that every edge connects a vertex from one set to the other. BFS-based detection: assign color 0 to the start node, then for each unvisited neighbor assign the opposite color. If a neighbor is already colored the same as the current node, the graph contains an odd cycle and is not bipartite. Process all connected components. Time is O(V + E). This is equivalent to checking if the graph has no odd-length cycles. Bipartite graphs are used in matching problems and recommender systems.

from collections import deque
def is_bipartite(graph):
    color = {}
    for start in range(len(graph)):
        if start in color: continue
        color[start] = 0
        q = deque([start])
        while q:
            u = q.popleft()
            for v in graph[u]:
                if v not in color:
                    color[v] = 1 - color[u]; q.append(v)
                elif color[v] == color[u]: return False
    return True

Cycle detection in a directed graph uses a three-state DFS coloring: WHITE (unvisited), GRAY (in current DFS path), BLACK (fully processed). Start DFS from each unvisited node. Mark it GRAY when entering, BLACK when all descendants are processed. If you encounter a GRAY node during DFS, a back edge (cycle) exists. This is because a GRAY node is currently on the recursion stack, so reaching it again means there is a path from it back to itself. Time is O(V + E). This is the basis for topological sort cycle detection and dependency resolution.

def has_cycle(n, edges):
    WHITE, GRAY, BLACK = 0, 1, 2
    g = [[] for _ in range(n)]
    for u, v in edges: g[u].append(v)
    color = [WHITE]*n
    def dfs(u):
        color[u] = GRAY
        for v in g[u]:
            if color[v]==GRAY: return True
            if color[v]==WHITE and dfs(v): return True
        color[u] = BLACK; return False
    return any(dfs(i) for i in range(n) if color[i]==WHITE)

Kahn's algorithm is a BFS-based topological sort. Compute in-degrees of all vertices. Add all zero-in-degree vertices to a queue. Repeatedly dequeue a vertex, add it to the result, and decrement the in-degree of its neighbors. If a neighbor's in-degree becomes zero, enqueue it. After processing, if the result contains fewer than V vertices, the remaining nodes (with non-zero in-degree) are part of cycles, detecting them implicitly. This provides both a topological ordering and cycle detection in O(V + E). It is preferred over DFS-based sort when an explicit ordering is needed level by level.

Dijkstra's algorithm finds shortest paths from a single source in a graph with non-negative edge weights. It uses a min-heap priority queue. Initialize all distances to infinity except the source (0). Repeatedly extract the minimum-distance vertex, then relax its neighbors: if dist[u] + w(u,v) < dist[v], update dist[v] and push (new_dist, v) to the heap. Skip stale heap entries by checking if the popped distance matches the recorded distance. With a binary heap, time is O((V + E) log V). With a Fibonacci heap, O(E + V log V). Fails with negative edges.

import heapq
def dijkstra(graph, src):
    dist = {node: float('inf') for node in graph}
    dist[src] = 0
    heap = [(0, src)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]: continue
        for v, w in graph[u]:
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(heap, (nd, v))
    return dist

Center expansion finds all palindromes by expanding from each possible center outward while characters match. There are 2n-1 centers: n centers for odd-length palindromes (each character) and n-1 centers for even-length palindromes (between adjacent characters). For each center, expand left and right while within bounds and characters match. Track the maximum palindrome found. Total time is O(n²) in the worst case (e.g., 'aaaa'). Space is O(1). Manacher's algorithm improves this to O(n) by reusing previously computed palindrome extents, but center expansion is more commonly asked in interviews.

def longest_palindrome(s):
    res = ""
    for i in range(len(s)):
        for l, r in [(i,i),(i,i+1)]:
            while l>=0 and r<len(s) and s[l]==s[r]:
                if r-l+1 > len(res): res=s[l:r+1]
                l-=1; r+=1
    return res

Number of Islands counts connected components of '1's in a binary grid. Treat each cell as a graph node with edges to four adjacent cells. DFS approach: iterate all cells; when a '1' is found, increment count and flood-fill by recursively marking all connected '1's as visited (change to '0'). BFS approach: push the cell into a queue and process level by level. Both run in O(m·n) time and O(m·n) space in the worst case (all '1's forming a snake). The problem directly models network connectivity, island counting, and region labeling.

def num_islands(grid):
    if not grid: return 0
    m, n, count = len(grid), len(grid[0]), 0
    def dfs(r, c):
        if r<0 or r>=m or c<0 or c>=n or grid[r][c]!='1': return
        grid[r][c]='0'
        for dr,dc in [(-1,0),(1,0),(0,-1),(0,1)]: dfs(r+dr,c+dc)
    for r in range(m):
        for c in range(n):
            if grid[r][c]=='1': count+=1; dfs(r,c)
    return count

Coin Change finds the minimum number of coins summing to a target amount. DP approach: dp[i] = min coins for amount i, filled bottom-up. Time is O(amount × coins). BFS approach: treat amount as a graph, each node's neighbors are reachable by subtracting a coin; BFS from amount 0 finds the shortest path to the target. BFS guarantees the minimum number of steps and terminates early at the first solution. DP computes all sub-amounts. For sparse coin sets and small targets, BFS can terminate faster; DP is preferred for multiple queries on the same coin set.

def coin_change(coins, amount):
    dp = [float('inf')] * (amount + 1)
    dp[0] = 0
    for c in coins:
        for a in range(c, amount+1):
            dp[a] = min(dp[a], dp[a-c]+1)
    return dp[amount] if dp[amount]!=float('inf') else -1

Jump Game II uses a greedy BFS-like approach. Track the current range reachable in the current number of jumps (current_end) and the farthest position reachable from any position in the current range (farthest). When you exhaust the current range (i reaches current_end), increment jumps and set current_end to farthest. This is equivalent to BFS on implicit levels. Time is O(n) and space is O(1). The greedy choice of always extending to the farthest reachable position from any point in the current 'wave' is provably optimal because each jump covers the maximum possible ground.

def jump(nums):
    jumps = farthest = curr_end = 0
    for i in range(len(nums)-1):
        farthest = max(farthest, i + nums[i])
        if i == curr_end:
            jumps += 1
            curr_end = farthest
    return jumps

The Largest Rectangle in Histogram finds the maximum area rectangle in a histogram with n bars. A monotonic increasing stack maintains indices of bars in increasing height order. For each bar: while the stack is non-empty and the current bar is shorter than the top, pop the top. The popped bar is the height of a rectangle whose right boundary is the current index and left boundary is the new stack top (or 0 if empty). Width = current index - left boundary - 1. Push a sentinel bar of height 0 at the end to flush the stack. Time is O(n), space is O(n).

def largest_rectangle(heights):
    heights.append(0)
    stack, max_area = [-1], 0
    for i, h in enumerate(heights):
        while stack[-1]!=-1 and heights[stack[-1]]>=h:
            height = heights[stack.pop()]
            width = i - stack[-1] - 1
            max_area = max(max_area, height*width)
        stack.append(i)
    return max_area

Meeting Rooms II asks for the minimum number of conference rooms needed to hold all meetings without conflicts. Sort meetings by start time. Use a min-heap of end times. For each meeting, if the heap's minimum end time is ≤ the current start time, a room is freed—pop the minimum (reuse the room). Push the current end time regardless. The heap size at any point represents the number of rooms currently in use; the maximum heap size ever encountered is the answer. Time is O(n log n) for sorting and heap operations. Space is O(n) for the heap.

import heapq
def min_meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[0])
    heap = []
    for s, e in intervals:
        if heap and heap[0] <= s:
            heapq.heapreplace(heap, e)
        else:
            heapq.heappush(heap, e)
    return len(heap)

To find all anagram start indices of pattern p in string s, use a fixed-size sliding window of size len(p). Maintain a character frequency count of the current window and compare it to p's frequency count. Initially compute the window over s[:len(p)]. As the window slides right, add the new character and remove the leftmost. If the two frequency maps are equal, an anagram starts at the current left index. Comparing two fixed-size (26 for lowercase letters) arrays is O(1), making the overall algorithm O(n) time and O(1) space.

from collections import Counter
def find_anagrams(s, p):
    res, pw = [], Counter(p)
    sw = Counter(s[:len(p)])
    if sw == pw: res.append(0)
    for i in range(len(p), len(s)):
        sw[s[i]] += 1
        sw[s[i-len(p)]] -= 1
        if sw[s[i-len(p)]] == 0: del sw[s[i-len(p)]]
        if sw == pw: res.append(i-len(p)+1)
    return res

With at most k transactions (buy+sell = 1 transaction), define dp[t][d] = max profit with at most t transactions on day d. Transition: dp[t][d] = max(dp[t][d-1], prices[d] - prices[m] + dp[t-1][m]) for all m < d. Naively O(k·n²). Optimize by maintaining a running maximum of prices[m] - dp[t-1][m] as m increases, reducing to O(k·n). Special case: if k ≥ n//2, unlimited transactions (greedy). If k=1, classic single buy-sell. If k=2, can be solved with forward and backward pass.

def max_profit_k(k, prices):
    n = len(prices)
    if k >= n//2:
        return sum(max(prices[i+1]-prices[i],0) for i in range(n-1))
    dp = [[0]*n for _ in range(k+1)]
    for t in range(1, k+1):
        max_so_far = -prices[0]
        for d in range(1, n):
            dp[t][d] = max(dp[t][d-1], prices[d]+max_so_far)
            max_so_far = max(max_so_far, dp[t-1][d]-prices[d])
    return dp[k][n-1]

LIS finds the length of the longest strictly increasing subsequence. The naive DP is O(n²): dp[i] = max(dp[j]+1) for all j < i where nums[j] < nums[i]. The O(n log n) approach maintains a list tails where tails[i] is the smallest tail element of all LIS of length i+1 found so far. For each number, binary search tails for the first element ≥ current; if found, replace it; else append. The length of tails is the LIS length. tails is always sorted (enabling binary search), and replacing maintains the invariant of smallest possible tails for each length.

import bisect
def length_of_lis(nums):
    tails = []
    for n in nums:
        pos = bisect.bisect_left(tails, n)
        if pos == len(tails): tails.append(n)
        else: tails[pos] = n
    return len(tails)

Spiral traversal visits an m×n matrix layer by layer from the outermost inward. Maintain four boundaries: top, bottom, left, right. Each pass traverses right across top, down along right, left across bottom (if top < bottom), and up along left (if left < right), then shrinks all four boundaries by one. Continue while top ≤ bottom and left ≤ right. This handles rectangular matrices and single-row/column edge cases. Time is O(m·n) since every cell is visited exactly once. Space is O(1) excluding the output. It is the foundation for generating a spiral matrix or rotating a matrix in place.

def spiral_order(matrix):
    res = []
    top, bottom, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
    while top<=bottom and left<=right:
        for c in range(left, right+1): res.append(matrix[top][c])
        top += 1
        for r in range(top, bottom+1): res.append(matrix[r][right])
        right -= 1
        if top<=bottom:
            for c in range(right, left-1, -1): res.append(matrix[bottom][c])
            bottom -= 1
        if left<=right:
            for r in range(bottom, top-1, -1): res.append(matrix[r][left])
            left += 1
    return res

N-Queens places n queens on an n×n board with no two queens sharing a row, column, or diagonal. Place one queen per row and use three sets: cols (occupied columns), diag1 (row-col is constant for '/' diagonals), diag2 (row+col is constant for '\\' diagonals). At each row, try each column; if none of the three sets contain the current (col, row-col, row+col), place the queen, add to sets, recurse, then remove (backtrack). This avoids the O(n²) board scan for constraint checking at each step, reducing check time to O(1). Total time is O(n!) in the worst case.

def solve_n_queens(n):
    res, cols, d1, d2 = [], set(), set(), set()
    board = [['.']*n for _ in range(n)]
    def bt(row):
        if row==n: res.append([''.join(r) for r in board]); return
        for c in range(n):
            if c in cols or row-c in d1 or row+c in d2: continue
            board[row][c]='Q'; cols.add(c); d1.add(row-c); d2.add(row+c)
            bt(row+1)
            board[row][c]='.'; cols.discard(c); d1.discard(row-c); d2.discard(row+c)
    bt(0); return res

Palindrome partitioning uses backtracking combined with DP precomputation. First, precompute a 2D boolean table is_palindrome[i][j] in O(n²) indicating whether substring s[i..j] is a palindrome using DP: is_palindrome[i][j] = (s[i]==s[j]) and is_palindrome[i+1][j-1]. Then backtrack: at each index, try all ending positions; if is_palindrome[start][end] is True, add s[start:end+1] to the current partition, recurse from end+1, and backtrack. Precomputing palindrome checks reduces the backtracking from O(n·2^n) to O(2^n). Total time including output generation is O(n·2^n).

def partition(s):
    n = len(s)
    dp = [[False]*n for _ in range(n)]
    for i in range(n-1, -1, -1):
        for j in range(i, n):
            dp[i][j] = s[i]==s[j] and (j-i<3 or dp[i+1][j-1])
    res, path = [], []
    def bt(start):
        if start==n: res.append(path[:]); return
        for end in range(start, n):
            if dp[start][end]:
                path.append(s[start:end+1]); bt(end+1); path.pop()
    bt(0); return res

Expression Add Operators inserts +, -, * between digits of a number string to hit a target value. Unlike simple subset/permutation backtracking, it requires tracking the last operand separately to handle multiplication correctly (multiplication has higher precedence than addition/subtraction). State includes the current position, current evaluation value, and the previous operand. For multiplication: new_val = cur_val - prev + (prev * digit), because multiplying revises the last addition/subtraction. This design avoids maintaining an expression stack, keeping the recursion O(1) per state step. Total time is O(4^n · n) due to branching factor 4 (three operators + split).

Interval DP solves problems defined over contiguous subarrays or substrings, where the optimal solution to interval [i,j] depends on smaller intervals. Matrix Chain Multiplication finds the minimum scalar multiplications to chain n matrices. Define dp[i][j] = min cost to multiply matrices i through j. Try all splits k: dp[i][j] = min(dp[i][k] + dp[k+1][j] + p[i-1]*p[k]*p[j]) for k in [i, j-1]. Fill in order of increasing interval length. Time is O(n³), space O(n²). The same pattern applies to Burst Balloons, Strange Printer, and Minimum Cost to Merge Stones.

def matrix_chain(p):
    n = len(p) - 1
    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):
                cost = dp[i][k]+dp[k+1][j]+p[i]*p[k+1]*p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    return dp[0][n-1]

A Trie (prefix tree) is a tree where each node represents one character and a path from root to a node spells a prefix. Each node has up to 26 children (for lowercase letters) and an is_end flag. Insert: traverse from root, creating nodes as needed, set is_end=True at the last character. Search: traverse, return False if any node is missing, return True only if is_end is set at the last character. StartsWith (prefix check): same as search but return True regardless of is_end at the last node. All operations are O(L) where L is word length. Space is O(total characters).

class TrieNode:
    def __init__(self): self.children={}; self.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.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.end

Producer-consumer in Python uses queue.Queue (thread-safe) or asyncio.Queue (async). Producers put items onto the queue; consumers get and process items. Queue.get() blocks until an item is available; Queue.put() blocks if maxsize is reached (bounded buffer). Sentinel values (None) signal consumers to stop. For thread-based: use threading.Thread for producers and consumers; for async: use asyncio.create_task with async def workers. This decouples production and consumption rates, enables parallel processing, and avoids busy-waiting. In ML pipelines, it parallels data loading with model forward passes.

from queue import Queue
from threading import Thread
def producer(q, items):
    for item in items: q.put(item)
    q.put(None)
def consumer(q):
    while True:
        item = q.get()
        if item is None: break
        print('processing', item)
q = Queue(maxsize=10)
Thread(target=producer, args=(q, range(20))).start()
Thread(target=consumer, args=(q,)).start()