When

• Sorted array with target sum/diff.
• Palindrome / reverse / partition in place.
• Merge two sorted sequences.
• Squared sorted array, dutch flag, remove duplicates.

Template

# opposing ends
def two_sum_sorted(a, target):
    l, r = 0, len(a) - 1
    while l < r:
        s = a[l] + a[r]
        if s == target: return [l, r]
        if s < target: l += 1
        else: r -= 1
    return []

# same direction (partition / dedup)
def remove_duplicates(a):
    w = 0
    for r in range(len(a)):
        if r == 0 or a[r] != a[r-1]:
            a[w] = a[r]; w += 1
    return w

Fixed-Size

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

Variable

# longest substring with at most K distinct chars
def longest_k_distinct(s, k):
    cnt = {}; l = 0; best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        while len(cnt) > k:
            cnt[s[l]] -= 1
            if cnt[s[l]] == 0: del cnt[s[l]]
            l += 1
        best = max(best, r - l + 1)
    return best

Floyd's Tortoise & Hare

def detect_cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next; fast = fast.next.next
        if slow is fast: break
    else: return None
    slow = head
    while slow is not fast:
        slow = slow.next; fast = fast.next
    return slow

Prefix Sum

p = [0] * (len(a) + 1)
for i, v in enumerate(a): p[i+1] = p[i] + v
# range sum [l, r] = p[r+1] - p[l]

# subarray sum equals K (count)
def count_k(a, k):
    seen = {0: 1}; s = 0; ans = 0
    for v in a:
        s += v
        ans += seen.get(s - k, 0)
        seen[s] = seen.get(s, 0) + 1
    return ans

Difference Array (range update)

# add v to a[l..r] in O(1); reconstruct in O(n)
d = [0] * (n + 1)
def update(l, r, v):
    d[l] += v; d[r+1] -= v
def build():
    a = [0] * n; cur = 0
    for i in range(n):
        cur += d[i]; a[i] = cur
    return a

Classic

def lower_bound(a, x):
    l, r = 0, len(a)
    while l < r:
        m = (l + r) // 2
        if a[m] < x: l = m + 1
        else: r = m
    return l   # first index with a[i] >= x

Binary Search on Answer

# minimum capacity to ship within D days
def feasible(cap, weights, D):
    days, cur = 1, 0
    for w in weights:
        if cur + w > cap: days += 1; cur = 0
        cur += w
    return days <= D

def min_capacity(weights, D):
    lo, hi = max(weights), sum(weights)
    while lo < hi:
        m = (lo + hi) // 2
        if feasible(m, weights, D): hi = m
        else: lo = m + 1
    return lo

BFS

from collections import deque
def bfs(start, adj):
    dist = {start: 0}
    q = deque([start])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if v not in dist:
                dist[v] = dist[u] + 1
                q.append(v)
    return dist

DFS

def dfs(u, adj, seen):
    seen.add(u)
    for v in adj[u]:
        if v not in seen: dfs(v, adj, seen)

# iterative
def dfs_iter(start, adj):
    stack = [start]; seen = {start}
    while stack:
        u = stack.pop()
        for v in adj[u]:
            if v not in seen:
                seen.add(v); stack.append(v)

Grid Walk

DIR = [(1,0),(-1,0),(0,1),(0,-1)]
def in_bounds(r, c, R, C): return 0 <= r < R and 0 <= c < C
# multi-source BFS for nearest-X distance, etc.

Template

def backtrack(path, choices):
    if is_solution(path):
        result.append(path[:]); return
    for c in choices:
        if not feasible(path, c): continue
        path.append(c)
        backtrack(path, next_choices(choices, c))
        path.pop()

Subsets / Permutations

def subsets(nums):
    out = []; cur = []
    def go(i):
        if i == len(nums): out.append(cur[:]); return
        go(i + 1)
        cur.append(nums[i]); go(i + 1); cur.pop()
    go(0); return out

Kahn's BFS

from collections import deque
def topo(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[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 adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0: q.append(v)
    return order if len(order) == n else []   # [] = cycle

Template

class DSU:
    def __init__(self, n):
        self.p = list(range(n)); self.r = [0] * n
    def find(self, x):
        while self.p[x] != x:
            self.p[x] = self.p[self.p[x]]   # path compression
            x = self.p[x]
        return x
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb: return False
        if self.r[ra] < self.r[rb]: ra, rb = rb, ra
        self.p[rb] = ra
        if self.r[ra] == self.r[rb]: self.r[ra] += 1
        return True

1D DP — House Robber

def rob(a):
    take = skip = 0
    for v in a:
        take, skip = skip + v, max(take, skip)
    return max(take, skip)

0/1 Knapsack

def knap(W, wt, val):
    dp = [0] * (W + 1)
    for i in range(len(wt)):
        for w in range(W, wt[i] - 1, -1):
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i])
    return dp[W]

LIS

from bisect import bisect_left
def lis(a):
    tails = []
    for x in a:
        i = bisect_left(tails, x)
        if i == len(tails): tails.append(x)
        else: tails[i] = x
    return len(tails)

Edit Distance

def edit(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(n+1): dp[i][0] = i
    for j in range(m+1): dp[0][j] = j
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1]
            else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
    return dp[n][m]

Interval DP

Burst balloons, matrix chain, palindrome partition. Iterate by length: for L in 2..n: for i in 0..n-L.

Bitmask DP

State = subset of n elements (n ≤ 20). TSP, assignments. dp[mask][i] = best ending at i covering mask.

Interval Scheduling

# max non-overlapping: sort by END
def max_intervals(iv):
    iv.sort(key=lambda x: x[1])
    end = -float('inf'); cnt = 0
    for s, e in iv:
        if s >= end: cnt += 1; end = e
    return cnt

# merge overlapping: sort by START
def merge(iv):
    iv.sort(); 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

Heap Greedy

Meeting rooms II, k closest, merge k sorted, dijkstra. Pattern: pop min, push derived.

Next Greater Element

def next_greater(a):
    n = len(a); res = [-1] * n; st = []
    for i in range(n):
        while st and a[st[-1]] < a[i]:
            res[st.pop()] = a[i]
        st.append(i)
    return res

Sliding Window Max

from collections import deque
def max_window(a, k):
    dq = deque(); out = []
    for i, v in enumerate(a):
        while dq and a[dq[-1]] <= v: dq.pop()
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()
        if i >= k - 1: out.append(a[dq[0]])
    return out

Common Tricks

x & (x - 1)         # clear lowest set bit
x & -x              # isolate lowest set bit
bin(x).count('1')   # popcount
x ^ y               # set of differing bits

# single number (others appear twice)
def single(a):
    r = 0
    for v in a: r ^= v
    return r

# subset enumeration of bitmask m
sub = m
while sub:
    process(sub)
    sub = (sub - 1) & m