Algorithmic Patterns

Two pointers replaces an O(n²) pair search with O(n) by exploiting monotonicity: when the data is sorted, moving a pointer inward strictly changes the sum in a known direction, so the discarded pairs are provably not answers. The variants matter: opposite-end (pair sums, container-with-most-water, palindrome checks), same-direction fast/slow (cycle detection, in-place dedup, partitioning), and the merge pattern (two sorted inputs consumed together).

def two_sum_sorted(a, target):
    lo, hi = 0, len(a) - 1
    while lo < hi:
        s = a[lo] + a[hi]
        if s == target:
            return lo, hi
        if s < target:
            lo += 1        # only way to increase
        else:
            hi -= 1        # only way to decrease
    return None

def has_cycle(head):          # Floyd: same pattern
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

A sliding window turns O(n·k) or O(n²) substring/subarray scans into O(n) by maintaining incremental state as the window moves, so recomputation is avoided. Fixed-size windows are simple ring arithmetic; variable-size windows expand right and shrink left while an invariant holds.

from collections import Counter, deque

def longest_at_most_k_distinct(s, k):
    count, lo, best = Counter(), 0, 0
    for hi, ch in enumerate(s):
        count[ch] += 1
        while len(count) > k:          # invariant broken
            count[s[lo]] -= 1
            if count[s[lo]] == 0:
                del count[s[lo]]
            lo += 1                    # shrink from the left
        best = max(best, hi - lo + 1)
    return best

def max_in_windows(a, k):              # monotonic deque, O(n)
    dq, out = deque(), []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v:
            dq.pop()                   # smaller values are useless
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

A prefix array P[i] = sum of the first i elements answers any range sum in O(1) after O(n) preprocessing. The difference array is its inverse: to add v over [l, r] record D[l] += v and D[r+1] -= v, then a single prefix pass materialises the result — turning m range updates from O(mn) into O(m + n).

from itertools import accumulate
from collections import Counter

a = [3, 1, 4, 1, 5, 9, 2]
P = [0] + list(accumulate(a))       # sentinel zero
P[5] - P[2]                         # sum of a[2:5] — O(1)

def range_add(n, updates):          # difference array
    D = [0] * (n + 1)
    for l, r, v in updates:
        D[l] += v
        D[r + 1] -= v               # O(1) per update
    return list(accumulate(D[:n]))  # materialise once

def count_subarrays_sum_k(a, k):    # works with negatives
    seen, run, total = Counter({0: 1}), 0, 0
    for v in a:
        run += v
        total += seen[run - k]
        seen[run] += 1
    return total

This pattern applies when the feasibility of a candidate answer is MONOTONE: if x works then everything above (or below) x works too. You then binary search the answer space with a predicate check(x), turning an intractable search into O(log(range) × cost of check).

def min_capacity(weights, days):
    def check(cap):                  # monotone in cap
        used, cur = 1, 0
        for w in weights:
            if cur + w > cap:
                used, cur = used + 1, 0
            cur += w
        return used <= days

    lo, hi = max(weights), sum(weights)
    while lo < hi:
        mid = (lo + hi) // 2
        if check(mid):
            hi = mid                 # feasible: try smaller
        else:
            lo = mid + 1             # infeasible: need bigger
    return lo

# O(n log(sum)) — the check is the algorithm,
# the binary search is just the wrapper

Backtracking is DFS over a space of partial solutions with three components: choose, explore, un-choose. Its cost is exponential in principle, so all practical performance comes from PRUNING — abandoning a branch as soon as a constraint is violated or a bound proves it cannot beat the current best.

def permutations(a):
    out, cur, used = [], [], [False] * len(a)
    def bt():
        if len(cur) == len(a):
            out.append(cur[:])       # copy!
            return
        for i, v in enumerate(a):
            if used[i]:
                continue
            used[i] = True; cur.append(v)      # choose
            bt()                                # explore
            cur.pop();    used[i] = False       # un-choose
    bt()
    return out

def n_queens(n):
    cols, d1, d2, out = set(), set(), set(), []
    def bt(r, board):
        if r == n:
            out.append(board[:]); return
        for c in range(n):
            if c in cols or r-c in d1 or r+c in d2:
                continue                        # PRUNE early
            cols.add(c); d1.add(r-c); d2.add(r+c)
            bt(r + 1, board + [c])
            cols.remove(c); d1.remove(r-c); d2.remove(r+c)
    bt(0, [])
    return out

A greedy algorithm commits to a locally optimal choice and never reconsiders. It is correct only when the problem has the greedy-choice property and optimal substructure, and the standard proof technique is the exchange argument: take any optimal solution, swap in the greedy choice, and show the result is no worse.

def max_meetings(intervals):
    # sort by EARLIEST FINISH — this key is the algorithm
    intervals.sort(key=lambda x: x[1])
    count, last_end = 0, float("-inf")
    for start, end in intervals:
        if start >= last_end:
            count += 1
            last_end = end
    return count

# greedy FAILS for coin change with arbitrary coins:
#   coins = [1, 3, 4], target = 6
#   greedy -> 4 + 1 + 1 = 3 coins
#   optimal -> 3 + 3     = 2 coins
# => needs DP

import heapq                       # greedy + heap: scheduling
def min_rooms(intervals):
    intervals.sort()
    ends = []
    for s, e in intervals:
        if ends and ends[0] <= s:
            heapq.heappop(ends)
        heapq.heappush(ends, e)
    return len(ends)

Divide and conquer splits input into independent subproblems, recurses, and combines. The Master Theorem gives the cost of T(n) = a·T(n/b) + f(n): merge sort (2T(n/2)+O(n)) is O(n log n), binary search (T(n/2)+O(1)) is O(log n), and Karatsuba multiplication (3T(n/2)+O(n)) is O(n^1.585), beating the schoolbook O(n²).

def count_inversions(a):
    if len(a) < 2:
        return a, 0
    mid = len(a) // 2
    left,  x = count_inversions(a[:mid])
    right, y = count_inversions(a[mid:])
    merged, cross = [], 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
            cross += len(left) - i      # the insight
    merged += left[i:] + right[j:]
    return merged, x + y + cross

# Master Theorem: T(n) = a T(n/b) + f(n)
#   2 T(n/2) + O(n)   -> O(n log n)   merge sort
#   3 T(n/2) + O(n)   -> O(n^1.585)   Karatsuba

Core identities worth knowing cold: x & (x−1) clears the lowest set bit (and counts bits in a loop); x & −x isolates it (the Fenwick step); x ^ x = 0 makes XOR a self-inverse, which solves "find the single unpaired element" in O(1) space; x << k and x >> k are multiply/divide by 2^k; and (x >> i) & 1 tests bit i. Bitmasks represent subsets so enumerating all 2^n subsets is a simple range loop, and iterating submasks of m is the s = (s−1) & m trick.

x & (x - 1)        # clear lowest set bit
x & -x             # isolate lowest set bit (Fenwick step)
x | (1 << i)       # set bit i
x & ~(1 << i)      # clear bit i
x ^ (1 << i)       # flip bit i
(x >> i) & 1       # test bit i
x.bit_count()      # popcount, Python 3.10+

def single_number(a):          # everything twice but one
    out = 0
    for v in a:
        out ^= v               # x ^ x == 0
    return out

# enumerate all subsets of n items
for mask in range(1 << n):
    subset = [a[i] for i in range(n) if mask >> i & 1]

# iterate submasks of m
s = m
while s:
    ...
    s = (s - 1) & m

KMP builds a failure/LPS array where lps[i] is the length of the longest proper prefix of pattern[0..i] that is also a suffix. On a mismatch, the pattern shifts so that this already-matched prefix aligns — the text pointer never moves backwards, giving O(n+m) total with O(m) space.

def build_lps(p):
    lps = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k and p[i] != p[k]:
            k = lps[k - 1]        # fall back within the pattern
        if p[i] == p[k]:
            k += 1
            lps[i] = k
    return lps

def kmp(text, p):
    lps, k, hits = build_lps(p), 0, []
    for i, ch in enumerate(text):     # i NEVER goes backwards
        while k and ch != p[k]:
            k = lps[k - 1]
        if ch == p[k]:
            k += 1
            if k == len(p):
                hits.append(i - k + 1)
                k = lps[k - 1]
    return hits

# O(n + m). Rolling hash alternative:
# h = (h - ord(old) * pow(B, m-1, M)) * B + ord(new)  mod M

Sweep line converts geometric or temporal overlap problems into event processing: emit (+1 at start, −1 at end), sort by coordinate, and maintain running state. Sorting dominates at O(n log n).

def merge_intervals(iv):
    iv.sort()                          # by start
    out = []
    for s, e in iv:
        if out and s <= out[-1][1]:
            out[-1][1] = max(out[-1][1], e)
        else:
            out.append([s, e])
    return out

def max_concurrent(iv):
    events = []
    for s, e in iv:
        events.append((s, +1))
        events.append((e, -1))
    # -1 before +1 at equal time => [start, end) semantics
    events.sort(key=lambda x: (x[0], x[1]))
    cur = best = 0
    for _, delta in events:
        cur += delta
        best = max(best, cur)
    return best

# O(n log n) — the sort dominates