Use the largest dimension and worst-case branching. Constants matter, but these are safe interview targets.

1. n <= 20: O(2^n), bitmask, meet-in-the-middle.
2. n <= 100: O(n^3) may pass; O(n^2) likely.
3. n <= 1,000: target O(n^2) or better.
4. n <= 100,000: target O(n log n) or O(n).
5. n >= 1,000,000: usually O(n), O(1)/O(n) space.
6. Small alphabet/value range: counting or state compression may replace sorting.

Cost

Budget memory too: 10^7 list references use about 80 MB; distinct Python integers push that beyond 300 MB.

"After every iteration, ____ is true." The invariant determines initialization, update order, and termination.

1. Window: current [left, right] satisfies the constraint after shrinking.
2. Binary search: every possible answer remains inside [lo, hi].
3. Traversal: every queued node has the promised distance/state.
4. DP: dp[state] stores exactly the answer named in one sentence.
5. Greedy: choices already committed can belong to an optimal solution.

Watch

Most bugs are broken invariants caused by updating an index, count, or visited set at the wrong time.

One pass O(n); sort O(n log n); balanced heap operations O(log n); full pair table O(mn); graph traversal O(V + E). Amortized O(1) means expensive operations are rare across the whole run.

1. Nested loops are not automatically O(n^2): count total pointer movement.
2. Recursion space includes call depth.
3. Sorting in Python can use O(n) auxiliary space.
4. Returning k answers costs at least O(k).

Membership/count -> dict/set. FIFO -> deque. Repeated min/max -> heapq. Sorted insertion/search -> bisect. Frequency -> Counter. Grouping -> defaultdict. Never use list.pop(0) for a queue.

from collections import Counter, defaultdict, deque
from functools import cache
from bisect import bisect_left
import heapq, math

INF = float("inf")
dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))

Watch

A tool does not justify an algorithm. Explain the invariant first, then why the operation supports it.

Store only the past needed to answer the current item in O(1) expected time.

seen = {}  # value -> earliest index
for i, x in enumerate(nums):
    need = target - x
    if need in seen:
        return seen[need], i
    if x not in seen:
        seen[x] = i

Cost

O(n) time, O(n) space.

Variations

Set for membership; map to index/count/best state; scan right-to-left for future information.

Watch

Check before insert when the same element cannot be reused.

Map each item to a stable signature, then count or group signatures.

groups = defaultdict(list)
for word in words:
    key = tuple(sorted(word))
    groups[key].append(word)

# Fixed alphabet: tuple(Counter(word)[c] for c in alphabet)

Cost

Usually O(total input); sorting each key adds O(k log k).

Variations

Counter subtraction, frequency buckets, Boyer-Moore for strict majority.

Watch

The key must preserve exactly the equivalence relation, no more and no less.

prefix[i] summarizes the first i items, so [l, r] is a difference of two prefixes.

prefix = [0]
for x in nums:
    prefix.append(prefix[-1] + x)

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

Cost

Build O(n); each query O(1); space O(n).

Variations

Prefix XOR, product where invertible, 2-D summed-area table, prefix/suffix extrema.

Watch

A leading identity value makes boundaries and empty prefixes uniform.

At prefix p, a previous prefix p-k creates a subarray summing to k.

count = {0: 1}
prefix = ans = 0
for x in nums:
    prefix += x
    ans += count.get(prefix - k, 0)
    count[prefix] = count.get(prefix, 0) + 1
return ans

Cost

O(n) time, O(n) space.

Variations

Store earliest index for longest; use prefix % k for divisible sums; encode balance as +1/-1.

Watch

Initialize state 0 before scanning so subarrays starting at index 0 count.

Record only where an effect starts and stops; one prefix pass materializes all values.

diff = [0] * n
for left, right, delta in updates:
    diff[left] += delta
    if right + 1 < n:
        diff[right + 1] -= delta

for i in range(1, n):
    diff[i] += diff[i - 1]

Cost

O(n + q) time, O(n) space.

Variations

Event map for sparse coordinates; 2-D rectangle updates; capacity validation while sweeping.

Watch

Define whether right endpoints are inclusive before writing the cancellation index.

Count how many answers include each element instead of generating every answer.

# nums[i] occurs in (i + 1) * (n - i) subarrays
total = 0
for i, x in enumerate(nums):
    total += x * (i + 1) * (len(nums) - i)

Cost

Often reduces O(n^2) enumeration to O(n).

Variations

Count as minimum/maximum using monotonic boundaries; count subsequences by combinatorics.

Watch

Prove each object is counted exactly once, usually by assigning a unique representative.

Use comparison to prove one boundary cannot participate in a better answer, then discard it.

left, right = 0, len(a) - 1
while left < right:
    value = f(a[left], a[right])
    if value == target:
        return left, right
    if value < target:
        left += 1
    else:
        right -= 1

Cost

O(n) after sorting; O(n log n) if sorting is required.

Variations

3Sum: fix one value then two-pointer the suffix; container: move shorter wall.

Watch

You need monotonic evidence that the discarded boundary is safe.

read examines every item; write marks the next valid output position.

write = 0
for read, x in enumerate(nums):
    if keep(x):
        nums[write] = x
        write += 1
return write  # valid prefix is nums[:write]

Cost

O(n) time, O(1) extra space.

Variations

Stable partition; Dutch national flag uses low/current/high; merge from the back.

Watch

Say whether order must be preserved; that changes which partition algorithm is legal.

Add the entering element and remove the leaving element rather than recomputing the block.

if len(nums) < k:
    return None
window = sum(nums[:k])
best = window
for right in range(k, len(nums)):
    window += nums[right]
    window -= nums[right - k]
    best = max(best, window)

Cost

O(n) time, O(1) or O(alphabet) space.

Variations

Rolling hash; Counter with a mismatch count; fixed-size deque.

Watch

Handle n < k explicitly if the prompt does not guarantee validity.

Expand right. While invalid, advance left until valid. Record only when the needed invariant holds.

left = 0
for right, x in enumerate(a):
    add(x)
    while not valid():
        remove(a[left])
        left += 1
    best = max(best, right - left + 1)

Cost

O(n): each item enters and leaves at most once.

Variations

Minimum window: shrink while valid and record before breaking validity.

Watch

This fails for exact-sum windows with arbitrary negatives because removing left is not monotone.

Every valid window ending at right contributes right-left+1 subarrays. exactly(K) = atMost(K) - atMost(K-1).

def at_most(k):
    left = ans = 0
    for right, x in enumerate(a):
        add(x)
        while score() > k:
            remove(a[left]); left += 1
        ans += right - left + 1
    return ans

Cost

O(n) time, O(state) space.

Variations

At least K via total - atMost(K-1); binary array sum via atMost.

Watch

The score must change predictably when boundaries move.

Store indices whose values decrease from front to back. Dominated values can never become a future maximum.

q = deque()
for i, x in enumerate(a):
    while q and a[q[-1]] <= x:
        q.pop()
    q.append(i)
    if q[0] <= i - k:
        q.popleft()
    if i >= k - 1:
        ans.append(a[q[0]])

Cost

O(n) time, O(k) space; each index enters/leaves once.

Variations

Increasing deque for minima; prefix sum + deque for shortest subarray at least K.

Watch

Store indices, not only values, so expired items can be removed.

Keep an inclusive interval containing every remaining candidate.

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

Cost

O(log n) time, O(1) space.

Variations

Rotated array: one half is always sorted; choose the half containing target.

Watch

Every branch must strictly shrink the interval.

Use half-open [lo, hi). On true, keep mid because it may be the first true.

lo, hi = 0, len(a)
while lo < hi:
    mid = (lo + hi) // 2
    if predicate(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

Cost

O(log n) predicate calls.

Variations

Last true by searching first false; upper bound uses x > target.

Watch

Define what returning n means. Verify predicate is monotone over the full domain.

Search candidate answer x. predicate(x) asks whether x is feasible; monotonic feasibility replaces construction.

lo, hi = min_possible, max_possible
while lo < hi:
    mid = (lo + hi) // 2
    if feasible(mid):
        hi = mid       # minimize feasible value
    else:
        lo = mid + 1
return lo

Cost

O(check_cost * log(answer_range)).

Variations

Capacity to ship, eating speed, split array, place items with minimum distance.

Watch

Derive tight safe bounds and prove the feasibility direction before coding.

Do not materialize. Convert a virtual 1-D index with row, col = divmod(mid, cols), or eliminate a row/column from a corner.

lo, hi = 0, rows * cols
while lo < hi:
    mid = (lo + hi) // 2
    r, c = divmod(mid, cols)
    if matrix[r][c] < target:
        lo = mid + 1
    else:
        hi = mid

Cost

O(log(mn)) for globally sorted flattening; O(m+n) for corner walk.

Variations

Count <= x per row to enable answer-space search for kth smallest.

Watch

Row-wise sorted alone does not imply globally flattenable order.

Choose a key that makes the next safe decision local. Preserve original indices only if the output needs them.

items = sorted(items, key=lambda x: (x.end, x.start))

# decorate when original positions matter
ordered = sorted((value, i) for i, value in enumerate(a))

Cost

O(n log n) time; Python sorting may use O(n) space.

Variations

Sort ascending one field and descending another to control ties.

Watch

Tie-breaking is part of correctness, especially for events, envelopes, and interval endpoints.

After sorting by start, only the last merged interval can overlap the next one.

intervals.sort()
merged = []
for start, end in intervals:
    if not merged or start > merged[-1][1]:
        merged.append([start, end])
    else:
        merged[-1][1] = max(merged[-1][1], end)

Cost

O(n log n) time, O(n) output.

Variations

Insert one interval by emit-before, merge-overlap, emit-after.

Watch

Decide whether touching [1,2] and [2,3] overlaps under the prompt's endpoint semantics.

Sort by end and commit the interval that frees the timeline earliest.

intervals.sort(key=lambda x: x[1])
end = -float("inf")
kept = 0
for start, finish in intervals:
    if start >= end:
        kept += 1
        end = finish

Cost

O(n log n) time, O(1) extra after sorting.

Variations

Minimum removals = n - kept; weighted intervals require DP, not this greedy rule. See the greedy proof checklist on page 11.

Watch

Sorting by start is not sufficient for maximizing count.

Convert intervals into signed events and process cumulative state in coordinate order.

events = []
for start, end in intervals:
    events.append((start, +1))
    events.append((end, -1))

active = best = 0
for _, delta in sorted(events):
    active += delta
    best = max(best, active)

Cost

O(n log n) time, O(n) space; sparse event map is equivalent.

Variations

Coordinate compression; heap active intervals; difference array for small coordinates.

Watch

Tie order encodes endpoints: for half-open [start, end), process -1 before +1 so touching intervals do not overlap.

Mark on entry, recursively/iteratively process neighbors, optionally combine results on return.

def dfs(node, parent):
    seen.add(node)
    result = base(node)
    for nei in graph[node]:
        if nei != parent and nei not in seen:
            child = dfs(nei, node)
            result = combine(result, child)
    return result

Cost

O(V+E) time, O(V) seen plus O(depth) stack.

Variations

Preorder acts before children; postorder combines children; color states detect directed cycles.

Watch

Deep recursion can exceed Python's limit; use an explicit stack when depth may be large.

FIFO order guarantees states are first reached with the fewest edges.

q = deque([(start, 0)])
seen = {start}
while q:
    node, dist = q.popleft()
    if goal(node):
        return dist
    for nei in neighbors(node):
        if nei not in seen:
            seen.add(nei)
            q.append((nei, dist + 1))

Cost

O(V+E) time, O(V) space.

Variations

Process len(q) items per level when level boundaries matter.

Watch

Mark seen when enqueuing, not dequeuing, to avoid duplicate queue entries.

A cell is a node; legal directional moves are edges. Mutate the grid or maintain seen.

def visit(sr, sc):
    stack = [(sr, sc)]
    grid[sr][sc] = BLOCKED
    while stack:
        r, c = stack.pop()
        for dr, dc in dirs:
            nr, nc = r + dr, c + dc
            if 0 <= nr < R and 0 <= nc < C and valid(nr, nc):
                grid[nr][nc] = BLOCKED
                stack.append((nr, nc))

Cost

O(RC) time, O(RC) worst-case space.

Variations

Boundary flood fill first for surrounded regions; 8 directions for diagonals.

Watch

Centralize bounds and validity checks; mark before pushing.

Enqueue all sources at distance 0. Ordinary BFS then expands the globally closest frontier.

q = deque()
for state in all_states:
    if is_source(state):
        q.append(state)
        dist[state] = 0

while q:
    cur = q.popleft()
    for nxt in neighbors(cur):
        if dist[nxt] == INF:
            dist[nxt] = dist[cur] + 1
            q.append(nxt)

Cost

O(states + transitions).

Variations

Reverse the direction: start from outcomes and compute distance backward.

Watch

Do not run one BFS per source; initialize one shared frontier.

Write one sentence for what dfs(node) returns. Children solve smaller identical problems; parent combines them.

best = 0
def dfs(node):
    nonlocal best
    if not node:
        return identity
    left = dfs(node.left)
    right = dfs(node.right)
    best = max(best, through(node, left, right))
    return extend(node, left, right)

Cost

Usually O(n) time, O(height) stack.

Variations

Return multiple facts as a tuple; carry path state downward for prefix/path problems.

Watch

The value returned upward may differ from the global answer passing through the node.

Walk once while redirecting each next edge. Keep the untouched suffix before overwriting the pointer.

prev, cur = None, head
while cur:
    nxt = cur.next
    cur.next = prev
    prev = cur
    cur = nxt
return prev

Cost

O(n) time, O(1) extra space.

Variations

Reverse [left, right], k-group reversal, reorder by split + reverse + merge.

Watch

Save cur.next first. Use a dummy node whenever the operation may replace the head.

Repeatedly take nodes with no remaining prerequisites. If not all nodes are emitted, a cycle exists.

indeg = [0] * n
for u in range(n):
    for v in graph[u]:
        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 graph[u]:
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
return order if len(order) == n else []

Cost

O(V+E) time, O(V+E) space.

Variations

Layer count gives minimum parallel semesters; min-heap gives lexicographically smallest order.

Watch

Build edge direction consistently: prerequisite -> dependent.

Best-first exploration: the first non-stale pop finalizes the shortest distance to that state.

dist = {start: 0}
heap = [(0, start)]
while heap:
    d, u = heapq.heappop(heap)
    if d != dist[u]:
        continue
    for v, w in graph[u]:
        nd = d + w
        if nd < dist.get(v, INF):
            dist[v] = nd
            heapq.heappush(heap, (nd, v))

Cost

O((V+E) log V) with adjacency lists and a heap.

Variations

0-1 BFS uses deque; A* adds admissible heuristic; state may include stops/mask/direction.

Watch

Dijkstra is invalid with negative edges. Skip stale heap entries.

Any simple shortest path has at most V-1 edges. Relax every edge V-1 times; another improvement signals a cycle.

dist[start] = 0
for _ in range(n - 1):
    changed = False
    for u, v, w in edges:
        if dist[u] != INF and dist[u] + w < dist[v]:
            dist[v] = dist[u] + w
            changed = True
    if not changed:
        break

for u, v, w in edges:
    if dist[u] != INF and dist[u] + w < dist[v]:
        return None  # reachable negative cycle

Cost

O(VE) time, O(V) space.

Variations

Bounded stops: copy previous distances each round so one round adds one edge.

Watch

For bounded stops, copy distances per round. Keep the final edge scan when cycle detection is required.

Each component has a representative. Path compression and union by size keep operations nearly constant.

parent = list(range(n)); size = [1] * n
def find(x):
    while x != parent[x]:
        parent[x] = parent[parent[x]]
        x = parent[x]
    return x
def union(a, b):
    a, b = find(a), find(b)
    if a == b: return False
    if size[a] < size[b]: a, b = b, a
    parent[b] = a; size[a] += size[b]
    return True

Cost

O((V+E) alpha(V)) time, O(V) space; alpha is inverse-Ackermann and effectively constant.

Variations

Kruskal sorts edges then unions; map arbitrary labels to ids.

Watch

Union-find answers connectivity, not actual paths or directed reachability.

State is the partial candidate. At each node, choose one legal option, recurse, then undo exactly that choice.

ans = []
def backtrack(state):
    if complete(state):
        ans.append(snapshot(state))
        return
    for choice in choices(state):
        if not valid(state, choice):
            continue
        apply(state, choice)
        backtrack(state)
        undo(state, choice)

Cost

Output-sensitive; often O(branching^depth * work per node).

Variations

Return on first solution for existence; count without storing snapshots.

Watch

Append a copy of mutable paths, not the same list reference.

A start index prevents generating the same combination in different orders.

def dfs(start):
    ans.append(path.copy())
    for i in range(start, len(a)):
        if i > start and a[i] == a[i - 1]:
            continue
        path.append(a[i])
        dfs(i + 1)
        path.pop()

Cost

O(n * 2^n) including copies for all subsets.

Variations

Use dfs(i+1) for each item once; dfs(i) when reuse is allowed; stop at len(path)==k.

Watch

Sort first if skipping duplicate values.

At each depth choose any unused item. With duplicates, skip equal siblings after sorting.

used = [False] * len(a)
def dfs():
    if len(path) == len(a):
        ans.append(path.copy()); return
    for i in range(len(a)):
        if used[i]: continue
        if i and a[i] == a[i-1] and not used[i-1]: continue
        used[i] = True; path.append(a[i])
        dfs()
        path.pop(); used[i] = False

Cost

O(n * n!) output time, O(n) search depth.

Variations

In-place swapping avoids used[] for distinct values.

Watch

Duplicate skip is at the same tree depth, represented by !used[i-1].

Track constraints incrementally; choose the most constrained variable; reject impossible lower/upper bounds before recursion.

def dfs(pos):
    if impossible(remaining, target):
        return
    if done(pos):
        record()
        return
    for choice in ordered_candidates(pos):
        if allowed(choice):
            place(choice)
            dfs(next_pos(pos))
            remove(choice)

Cost

Same worst-case class, often dramatically fewer visited states.

Variations

Sort candidates; branch on rarest option; cache only when future depends solely on immutable state.

Watch

A prune must be a proof that no completion exists, not a guess.

Write brute force first, then cache by the minimal immutable state.

@cache
def dp(i, state):
    if terminal(i, state):
        return base_value
    best = identity
    for choice in legal(i, state):
        best = combine(best, value(choice) +
                       dp(next_i, next_state))
    return best

Cost

O(number of states * transitions per state).

Variations

Return bool/count/min/max; use tuple state; reconstruct via recorded choice.

Watch

Do not cache functions that depend on mutable globals not represented in the key.

Define dp[i] for a prefix or endpoint. If dependency distance is fixed, keep only a rolling window.

prev2, prev1 = base0, base1
for x in a:
    cur = max(prev1, prev2 + value(x))  # skip / take
    prev2, prev1 = prev1, cur
return prev1

Cost

Usually O(n) time; O(1) space when only recent states matter.

Variations

Climbing stairs, house robber, decode ways, min cost.

Watch

Save old values before overwriting; handle empty and length-one inputs.

For each item, update capacities backward so it cannot feed another state in the same round.

dp = [False] * (capacity + 1)
dp[0] = True
for weight in weights:
    for cap in range(capacity, weight - 1, -1):
        dp[cap] = dp[cap] or dp[cap - weight]

Cost

O(n * capacity) time, O(capacity) space.

Variations

Store max value, number of ways, or minimum items; subset sum is boolean knapsack.

Watch

Backward loop means use once. This direction is part of the algorithm.

Update capacity forward so the current item can extend a state created in the same round.

ways = [0] * (amount + 1)
ways[0] = 1
for coin in coins:
    for total in range(coin, amount + 1):
        ways[total] += ways[total - coin]

Cost

O(n * amount) time, O(amount) space.

Variations

Coins outer counts combinations; totals outer counts ordered sequences.

Watch

Loop order changes the mathematical objects being counted.

dp[r][c] combines reachable predecessor cells. One row suffices when dependencies are top and left.

row = [INF] * cols
row[0] = 0
for r in range(rows):
    for c in range(cols):
        if blocked(r, c):
            row[c] = INF
            continue
        top = row[c]
        left = row[c - 1] if c else INF
        row[c] = cost[r][c] + min(top, left)

Cost

O(RC) time, O(C) space.

Variations

Count paths uses +; max reward uses max; arbitrary movement becomes graph search.

Watch

Reset blocked cells so an old value from the previous row cannot leak through.

dp[i][j] answers for prefixes a[:i] and b[:j]. Matching items use diagonal; mismatch drops one side.

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

Cost

O(mn) time and space; often O(n) space with rolling rows.

Variations

LCS, interleaving, distinct subsequences, wildcard matching.

Watch

A padded zero row/column represents empty prefixes and removes boundary branches.

At mismatch, the final operation corresponds to left (insert), top (delete), or diagonal (replace).

prev = list(range(n + 1))
for i in range(1, m + 1):
    cur = [i] + [0] * n
    for j in range(1, n + 1):
        if a[i - 1] == b[j - 1]:
            cur[j] = prev[j - 1]
        else:
            cur[j] = 1 + min(cur[j - 1],
                             prev[j],
                             prev[j - 1])
    prev = cur

Cost

O(mn) time, O(n) space.

Variations

Weighted operations; deletion-only distance derives from LCS.

Watch

Name what each neighbor means to avoid swapping insert and delete.

Fill shorter intervals before longer ones. Choose the last/first pivot so remaining pieces become independent.

for length in range(1, n + 1):
    for left in range(n - length + 1):
        right = left + length - 1
        dp[left][right] = identity
        for k in range(left, right + 1):
            dp[left][right] = best(
                dp[left][right],
                combine(left, k, right))

Cost

Commonly O(n^3) time, O(n^2) space.

Variations

Burst balloons, matrix-chain multiplication, palindrome partition/game.

Watch

Padding boundaries can make the chosen-last recurrence much cleaner.

Maintain the best k seen. The heap root is the weakest retained candidate.

heap = []
for item in stream:
    score = key(item)
    if len(heap) < k:
        heapq.heappush(heap, (score, item))
    elif score > heap[0][0]:
        heapq.heapreplace(heap, (score, item))

Cost

O(n log k) time, O(k) space.

Variations

For k-smallest, retain a max-heap and replace its largest item. Heapify all is O(n) when all data is present.

Watch

Tuple ties compare later fields; add a unique counter for non-comparable payloads.

Only the current head of each source can be globally next.

heap = []
for source, seq in enumerate(seqs):
    if seq:
        heapq.heappush(heap, (seq[0], source, 0))
while heap:
    value, s, i = heapq.heappop(heap)
    emit(value)
    if i + 1 < len(seqs[s]):
        heapq.heappush(heap, (seqs[s][i+1], s, i+1))

Cost

O(N log k) time, O(k) space.

Variations

Linked lists store node and source counter; smallest range tracks current maximum.

Watch

Heap size is number of streams, not total items.

Max-heap low and min-heap high; all low <= all high; sizes differ by at most one.

heapq.heappush(low, -x)
heapq.heappush(high, -heapq.heappop(low))
if len(high) > len(low):
    heapq.heappush(low, -heapq.heappop(high))

median = (-low[0] if len(low) > len(high)
          else (-low[0] + high[0]) / 2)

Cost

O(log n) insert, O(1) median, O(n) space.

Variations

Sliding median needs lazy deletion or an ordered multiset.

Watch

Maintain ordering and size invariants after every insertion.

Scan the current reachable prefix and track the farthest next boundary.

jumps = 0
current_end = farthest = 0
for i in range(len(a) - 1):
    farthest = max(farthest, i + a[i])
    if i == current_end:
        jumps += 1
        current_end = farthest

Cost

O(n) time, O(1) space.

Variations

Feasibility only keeps farthest; gas station resets candidate after negative prefix.

Watch

If unreachable input is allowed, detect when farthest does not advance.

Keep unresolved indices in monotone order. A new value resolves dominated stack entries.

stack = []
for i, x in enumerate(a):
    while stack and a[stack[-1]] < x:
        j = stack.pop()
        answer[j] = i - j
    stack.append(i)

Cost

O(n) time, O(n) space; each index pushes/pops once.

Variations

Histogram uses an increasing stack + sentinel; monotonic deque handles a moving window (page 3).

Watch

Choose < versus <= deliberately when duplicates can own the same boundary.

best_ending_here either extends the previous subarray or restarts at current value.

ending = best = nums[0]
for x in nums[1:]:
    ending = max(x, ending + x)
    best = max(best, ending)
return best

Cost

O(n) time, O(1) space.

Variations

Track indices; circular max = total - minimum subarray, except the all-negative case.

Watch

Initializing to 0 incorrectly allows an empty subarray when one element is required.

Each node represents a prefix. Following one symbol advances every word sharing that prefix at once.

root = {}
END = "#"
for word in words:
    node = root
    for ch in word:
        node = node.setdefault(ch, {})
    node[END] = True

Cost

Build O(total characters); query O(word length); space O(total characters).

Variations

DFS through trie + board for Word Search II; bitwise trie greedily chooses opposite bits for max XOR.

Watch

Prefix existence is not word existence; keep an explicit end marker.

tree[i] stores a power-of-two suffix of the prefix ending at i. The lowest set bit jumps between responsible ranges.

tree = [0] * (n + 1)
def add(i, delta):
    i += 1
    while i <= n:
        tree[i] += delta
        i += i & -i

def prefix(i):
    total = 0
    while i > 0:
        total += tree[i]
        i -= i & -i
    return total

Cost

O(log n) update/query, O(n) space; range(l,r) = prefix(r+1)-prefix(l).

Variations

Coordinate-compress values for count-smaller; segment tree supports richer associative queries.

Watch

The internal tree is 1-indexed; define whether prefix(i) includes index i before using it.

Every palindrome has one of 2n-1 centers. Expand equally left and right while characters match.

def expand(left, right):
    while left >= 0 and right < len(s) \
          and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1

best = max(expand(i, i) for i in range(len(s)))
best = max(best, *(expand(i, i + 1)
                   for i in range(len(s) - 1)))

Cost

O(n^2) time, O(1) extra space.

Variations

Count during expansion; Manacher finds all palindrome radii in O(n).

Watch

Check both odd center (i,i) and even center (i,i+1).

lps[i] is the longest proper prefix of pattern[:i+1] that is also a suffix. On mismatch, jump to the next viable prefix.

lps = [0] * len(p)
j = 0
for i in range(1, len(p)):
    while j and p[i] != p[j]:
        j = lps[j - 1]
    if p[i] == p[j]: j += 1
    lps[i] = j

j = 0
for i, ch in enumerate(text):
    while j and ch != p[j]: j = lps[j - 1]
    if ch == p[j]: j += 1
    if j == len(p): return i - len(p) + 1

Cost

O(text + pattern) time, O(pattern) space.

Variations

Z-algorithm for prefix matches; rolling hash for many substring comparisons with collision care.

Watch

Handle an empty pattern before indexing p[j].

XOR cancels equal values; x & (x-1) clears the lowest set bit; shifts test/set membership.

has_i = (mask >> i) & 1
mask |= 1 << i          # add i
mask &= ~(1 << i)       # remove i
mask ^= 1 << i          # toggle i
lowbit = mask & -mask
is_power2 = x > 0 and (x & (x - 1)) == 0

Cost

O(1) per machine-word operation; O(number of set bits) to enumerate.

Variations

Enumerate subsets: sub=(sub-1)&mask; prefix XOR answers range XOR.

Watch

Parenthesize shifts/comparisons and handle Python's unbounded signed integers deliberately.

Euclid reduces gcd; modular identities keep values bounded; exponentiation by squaring halves the exponent.

g = math.gcd(a, b)
lcm = a // g * b

def mod_pow(x, n, mod):
    ans = 1
    while n:
        if n & 1: ans = ans * x % mod
        x = x * x % mod
        n >>= 1
    return ans

Cost

GCD/power O(log value).

Variations

Sieve primes O(n log log n); modular inverse via pow(x, mod-2, mod) only under valid assumptions.

Watch

Divide before multiply in fixed-width languages; normalize negative modulo when semantics differ.

The sieve crosses out multiples once from each prime; trial factorization only needs candidates through sqrt(n).

is_prime = [True] * (n + 1)
is_prime[:2] = [False, False]
for p in range(2, int(n ** 0.5) + 1):
    if is_prime[p]:
        for x in range(p * p, n + 1, p):
            is_prime[x] = False

factors = []
d = 2
while d * d <= x:
    while x % d == 0:
        factors.append(d); x //= d
    d += 1

Cost

Sieve O(n log log n) time, O(n) space; one factorization O(sqrt(n)).

Variations

Smallest-prime-factor sieve answers many factorizations; segmented sieve handles large intervals.

Watch

Start crossing at p*p; smaller multiples were handled by smaller prime factors.

Count equivalent choices algebraically instead of enumerating them. Divide by symmetries only when the arithmetic permits.

# Multiplicative n choose k
k = min(k, n - k)
choose = 1
for i in range(1, k + 1):
    choose = choose * (n - k + i) // i

# With prime MOD, precompute factorials and inverses:
nCk = fact[n] * inv_fact[k] % MOD
nCk = nCk * inv_fact[n - k] % MOD

Cost

O(k) for one exact nCk; O(N) precompute then O(1) modular queries.

Variations

Stars and bars, inclusion-exclusion, Catalan structures, permutation counts with duplicates.

Watch

Ordinary division is invalid modulo M; use modular inverses only when the denominator is invertible.