Coding Patterns interview questions

What they're looking for: clear thinking and communication, not just a correct answer. Interviewers often prefer a candidate who reasons out loud to one who silently writes perfect code.

A reliable routine:

1. Understand: restate the problem, ask about input size, edge cases (empty input, duplicates, negatives), and the expected output format.
2. Examples: work through one small example by hand, plus one tricky case.
3. Brute force first: describe the simplest correct approach and its complexity. It proves you understand the problem.
4. Spot the pattern: use the clues below to find a faster approach, and explain the improvement.
5. Code it: clean names, small helper functions, talk while you type.
6. Test: run your examples through the code by hand; check the edge cases.
7. Analyse: state the final time and space complexity, and possible follow-ups.

Clues that point to a pattern:

Big-O describes how running time (or memory) grows as the input size n grows, ignoring constants and smaller terms. 3n² + 10n + 7 is O(n²).

Rules of thumb:

• Sequential steps add: O(n) + O(n log n) = O(n log n).
• Nested loops multiply: a loop inside a loop over the same input is O(n²).
• Halving the problem each step gives O(log n).
• Recursion: (number of calls) × (work per call). Naive Fibonacci makes ~2ⁿ calls.
• Space counts extra memory: new lists, dicts, and the recursion stack (depth d means O(d)).

Seeing it in practice:

Input size hints: n up to ~10⁵–10⁶ needs O(n) or O(n log n); n ≤ ~1,000 allows O(n²); n ≤ ~20 suggests an exponential approach (backtracking, bitmasks) is expected.

Pattern: hash map of values you've already seen.

For each number, the partner you need is target - n. Instead of searching for it (O(n) each time), look it up in a dict of numbers seen so far (O(1)).

Follow-ups: return all pairs; the input is sorted (use two pointers, O(1) space); count pairs with a given difference.

Pattern: hash map from a canonical key to a group.

Anagrams contain the same letters, so they share a key: the sorted letters ("eat" → "aet"), or a count of each letter (faster for long words).

Complexity for n words of length up to k: sorting keys is O(n · k log k); counting keys is O(n · k). Space O(n · k).

The general idea, "normalise each item to a key, then group by key", solves many problems: grouping shifted strings, isomorphic strings, and finding duplicate files by content hash.

Pattern: count with a hash map, then select the top k with a heap or bucket sort.

Why a min-heap of size k: keep the k best so far; the smallest of them is at the top, ready to be replaced. heapq.nlargest does exactly this.

Pattern: hash set for O(1) membership, and only start counting at the beginning of a run.

Sorting would give O(n log n). To get O(n): put everything in a set. A number x starts a sequence only if x - 1 is not in the set. From each start, count upward.

Why it's O(n), not O(n²): the inner while only runs from run starts, and each number is visited by the inner loop once across all runs. Total work is about 2n.

Lesson: the trick of "only do the expensive work at the start of something" turns many nested loops into linear time.

Pattern: two pointers moving towards each other.

Start with one pointer at each end. If the sum is too small, move the left pointer right (bigger numbers); if too big, move the right pointer left. Each step rules out one element for good.

index:   0   1   2   3   4   5
value:   1   3   4   6   8  11
         ^                   ^
       left                right
 
target 10:  1 + 11 = 12  too big   -> move the right pointer left
            1 +  8 =  9  too small -> move the left pointer right
            3 +  8 = 11  too big   -> move the right pointer left
            3 +  6 =  9  too small -> move the left pointer right
            4 +  6 = 10  found (indexes 2 and 3)

Time O(n), space O(1), compared with O(n) space for the hash-map version.

Two pointers also solve: removing duplicates from a sorted array in place, checking palindromes, reversing in place, merging two sorted arrays, and 3-Sum (fix one number, two-pointer the rest).

Pattern: sort, then for each number run two pointers on the rest. The main difficulty is skipping duplicates.

Complexity: sorting O(n log n) + n two-pointer passes of O(n) = O(n²), which is the best known for this problem. Space O(1) beyond the output (or O(n) for the sorted copy).

Why not a set of triplets from brute force? O(n³), and deduplicating afterwards is messy. Sorting makes duplicates adjacent, so skipping them is easy.

The same structure solves 3Sum Closest and 4Sum (one more outer loop).

Given heights h, the water between lines i and j is min(h[i], h[j]) * (j - i). Find the maximum.

Pattern: two pointers from both ends, always moving the shorter line inward.

Why that's safe: the area is limited by the shorter line. Moving the taller line inward can only make the width smaller while the height stays limited by the same short line, so it can never help. Moving the shorter one is the only move that might find a bigger area.

Time O(n) instead of O(n²) for trying every pair; space O(1).

In the interview, the proof (why skipping is safe) matters as much as the code. Explaining "the shorter side is the bottleneck" is what interviewers want to hear.

Pattern: variable-size sliding window. Expand the right edge one character at a time; when the window breaks the rule (a repeated character), shrink it from the left until it's valid again.

s = a b c a b c b b
 
[a b c] a b c b b     window "abc", length 3
 a [b c a] b c b b    "a" repeated: move start past the first "a"
 a b [c a b] c b b    "b" repeated: move start past the first "b"
 ...
longest window without repeats: 3

Each character enters and leaves the window at most once: O(n) time, O(k) space for k distinct characters.

The sliding-window template:

start = 0
for end in range(len(items)):
    add items[end] to the window state
    while the window is invalid:
        remove items[start] from the window state
        start += 1
    update the answer using the window [start, end]

Use it for "longest/shortest contiguous subarray or substring such that...": at most k distinct characters, sum at least target, minimum window containing all letters of a word.

Pattern: fixed-size sliding window. Instead of summing each window from scratch (O(n·k)), slide it: add the element entering on the right, subtract the one leaving on the left.

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

Related fixed-window problems:

• moving average of the last k values (use a deque);
• does the string contain a permutation of a pattern? (slide a window of the pattern's length, compare letter counts);
• maximum in every window of size k (a monotonic deque, O(n)).

If the window size isn't fixed ("smallest subarray with sum at least S"), use the variable-size window from the previous question.

Pattern: variable sliding window with counts: expand until the window contains everything, then shrink from the left while it still does, recording the smallest.

Time O(|s| + |t|): each index enters and leaves the window once. Space O(k) for the counts.

The missing counter is the key trick: it tells you in O(1) whether the window is valid, instead of comparing two whole count tables at each step.

Pattern: prefix sums + hash map.

The sum of nums[i+1..j] equals prefix[j] - prefix[i]. So a subarray ending at j sums to k exactly when some earlier prefix equals prefix[j] - k. Count earlier prefixes in a dict as you go.

Sliding window doesn't work here because numbers can be negative: growing the window doesn't always increase the sum.

Time O(n), space O(n), versus O(n²) for checking every subarray.

Other prefix-sum uses:

• range sum queries in O(1) after O(n) setup: sum(i..j) = prefix[j + 1] - prefix[i];
• longest subarray with sum k (store the first index of each prefix instead of a count);
• subarrays divisible by k (key = prefix % k);
• 2D prefix sums for rectangle sums in a grid.

Return an array where answer[i] is the product of all elements except nums[i], in O(n), without division (division also fails with zeros).

Pattern: prefix and suffix products. answer[i] = (product of everything to the left of i) × (product of everything to the right of i).

Time O(n); space O(1) extra (the output array doesn't count), because the left products are stored in the answer and the right products in one variable.

The "combine information from the left and from the right" idea appears in many problems: trapping rain water (max height on each side), candy distribution, and the longest mountain in an array.

Binary search finds a target in a sorted array by halving the search range each step: O(log n). A million items take about 20 steps.

It's famous for off-by-one bugs. A safe template: search for the first index where a condition becomes true.

Why this template is safe:

• the loop ends when lo == hi, so there's no "should it be < or <=?" question;
• each step strictly shrinks the range, so it can't loop forever;
• it naturally handles duplicates (first occurrence) and "not found" (returns hi).

bisect_left gives the first position where the target could be inserted; bisect_right gives the position after the last copy. Their difference counts occurrences in O(log n).

A sorted array was rotated at an unknown point ([4, 5, 6, 7, 0, 1, 2]). Find a target in O(log n).

Key insight: at any mid, at least one half is still sorted. Check whether the target lies inside the sorted half; if yes, search there, otherwise search the other half.

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

Related: find the minimum in a rotated array (compare nums[mid] with nums[hi]: if bigger, the minimum is to the right). With duplicates allowed, the worst case becomes O(n), because nums[lo] == nums[mid] == nums[hi] doesn't tell you which half is sorted.

Sometimes you binary-search over possible answers, not over an array. It works when you can check "is answer X good enough?" and the checks are monotonic: if X works, every bigger X works too.

Koko Eating Bananas: piles of bananas, h hours. Each hour Koko eats up to k bananas from one pile. Find the minimum speed k to finish in time.

• Checking a speed is easy: hours needed = sum(ceil(pile / k)).
• If speed k works, any faster speed works: monotonic. So binary search k between 1 and max(piles).

Time O(n log M) where M is the largest pile, versus O(n · M) trying every speed.

Other "binary search on the answer" problems: minimum ship capacity to deliver packages in D days, splitting an array into k parts minimising the largest sum, the smallest divisor under a threshold, and sqrt(x) rounded down. Clue: "find the minimum/maximum value such that a condition holds".

Pattern: stack. Push each opening bracket; for each closing bracket, the top of the stack must be its matching opener.

Time O(n), space O(n).

A stack fits whenever the most recent unmatched thing must be handled first (last in, first out): nested structures, undo, evaluating expressions (3 + 4 * 2), simplifying file paths (/a/./b/../c → /a/c), decoding strings like 3[a2[c]], and converting recursion into a loop.

Daily Temperatures: for each day, how many days until a warmer temperature? (0 if never.)

Brute force checks every later day: O(n²). A monotonic stack does it in O(n): keep a stack of indexes whose temperatures are decreasing. When a warmer day arrives, it's the answer for every colder day on top of the stack, so pop them.

Each index is pushed and popped at most once, so it's O(n) overall, even with the inner while.

Clues for a monotonic stack: "next greater / next smaller element", "how far until...", "largest rectangle in a histogram", "remove k digits to make the smallest number", stock span. Choose increasing or decreasing order depending on whether you're looking for greater or smaller values.

Pattern: walk the list once, turning each next pointer around. Keep three references: prev, current, and the saved next.

Iterative: O(n) time, O(1) space. Recursive: O(n) time, O(n) space for the call stack.

Linked-list tips: draw the pointers on paper; use a dummy head node to avoid special cases when the head might change (merging lists, removing elements); and test with 0, 1 and 2 nodes.

Pattern: two pointers moving at different speeds: slow moves 1 step, fast moves 2.

• Middle of the list: when fast reaches the end, slow is in the middle.
• Cycle detection (Floyd's algorithm): if there's a loop, fast eventually laps slow and they meet. If fast reaches None, there's no cycle.

Both run in O(n) time and O(1) space. A set of visited nodes also detects cycles, but uses O(n) memory.

The same idea finds a duplicate number in an array of n+1 values in 1..n (treat values as "next" pointers), and checks whether a number is "happy".

Pattern: two pointers, one per list; repeatedly take the smaller head. A dummy node avoids special-casing the first element.

Time O(n + m), space O(1) for linked lists (nodes are re-linked, not copied).

This merge step is the heart of merge sort. For k sorted lists, use a heap (see "Merge K Sorted Lists").

Pattern: sort by start, then sweep: each interval either overlaps the last merged one (extend it) or starts a new one.

Time O(n log n) for sorting; the sweep is O(n).

Clarify with the interviewer: do touching intervals ([1, 4] and [4, 5]) count as overlapping? Here they do (<=).

Related problems: insert a new interval into a sorted list; total covered length; free time across several calendars; and the minimum number of intervals to remove so the rest don't overlap (a greedy problem: sort by end and keep the earliest-ending ones).

Pattern: sort meetings by start time; keep a min-heap of end times for rooms in use. For each meeting, if the earliest-ending room is free by its start time, reuse it; otherwise open a new room. The heap's size is the answer.

Both are O(n log n).

The sweep line idea (turn intervals into +1/−1 events and sort them) answers "the maximum number of overlapping things at any moment": servers needed, peak concurrent users, platforms at a train station.

The simpler Meeting Rooms I (can one person attend everything?) only needs to sort and check whether any meeting starts before the previous one ends.

Pattern: a min-heap of size k. Keep the k largest values seen so far; the smallest of them (the heap's top) is the k-th largest.

Python's heapq is a min-heap. For a max-heap, push negated values (-x).

Pattern: a min-heap holding the current smallest item of each list. Pop the smallest, output it, and push the next item from the same list.

With N total items in k lists: O(N log k) time (each item goes through a heap of size k), O(k) extra space.

Notice the list index in the tuple: if two values are equal, Python compares the next field, and the index guarantees a valid comparison. (With linked-list nodes, which can't be compared, this tie-breaker is essential.)

Alternative: divide and conquer, merging lists in pairs (like merge sort), also O(N log k).

Real-world use: merging sorted files that don't fit in memory (external sort), and combining sorted results from database shards.

Pattern: two heaps. A max-heap holds the smaller half of the numbers; a min-heap holds the larger half. Keep them balanced (sizes differ by at most 1), so the median is always at the top of one or both.

add is O(log n), median is O(1).

Follow-ups:

• Sliding-window median (median of the last k values): you also need to remove old values; use lazy deletion or a sorted container.
• If all numbers are in a small range (say 0–100), a count array gives the median in O(100).
• Approximate percentiles over huge streams (p95 latency) use sketches like t-digest.

Pattern: depth-first search (DFS) with recursion. Most tree problems follow one shape: solve the problem for the left and right subtrees, then combine the answers at the current node.

Time O(n) (every node once); space O(h) for the recursion, where h is the height: O(log n) for a balanced tree, O(n) for a skewed one.

The same "combine the children's answers" recursion solves: tree size and sum, balanced tree check, diameter (longest path: left depth + right depth at each node), same tree / symmetric tree, path sum, and invert (mirror) a tree.

DFS orders: pre-order (node, left, right), in-order (left, node, right: gives a BST's values sorted), post-order (left, right, node: when you need children's results first, as here).

Pattern: breadth-first search (BFS) with a queue, processing the tree one level at a time.

Time O(n); space O(w), the maximum width of the tree (up to n/2 for the last level of a full tree).

The for _ in range(len(queue)) loop is the trick: it separates levels without storing depths.

BFS answers: level averages, right-side view, zigzag order, minimum depth (the first leaf found by BFS is the shallowest), and connecting nodes on the same level.

BFS vs DFS: use BFS when you care about levels or the shortest distance; use DFS for paths, subtree results and when the tree is very wide.

In a binary search tree (BST), every value in a node's left subtree is smaller than the node, and every value in its right subtree is larger.

Common mistake: only checking each node against its direct children. In this tree, 3 is a valid left child of 7, but it sits in the right subtree of 5, so it must be larger than 5. The tree is invalid:

Pattern: pass down the allowed range (low, high); going left narrows the upper bound, going right narrows the lower bound.

Time O(n), space O(h).

Other BST questions: search and insert (O(h)), k-th smallest (in-order traversal, stop at k), lowest common ancestor in a BST (walk down: if both values are smaller go left, both larger go right, otherwise you're at the split point), and converting a sorted array to a balanced BST.

The lowest common ancestor (LCA) of nodes p and q is the deepest node that has both in its subtree (a node counts as its own descendant).

Pattern: post-order DFS that reports what it found upward:

• if the current node is p or q, return it;
• search both subtrees;
• if both sides found something, the current node is the LCA;
• otherwise pass up whichever side found something.

Time O(n), space O(h). (This version assumes both values exist in the tree.)

Variations:

• In a BST, it's O(h) without searching both sides: walk down until p and q are on different sides.
• With parent pointers, it becomes "the first common node of two linked lists".
• Many queries on a fixed tree: preprocess with binary lifting for O(log n) per query.

Pattern: treat the grid as a graph (each cell connects to its 4 neighbours). Scan every cell; each unvisited land cell starts a new island, and a flood fill (DFS or BFS) marks the whole island as visited.

Time O(rows × cols): each cell is visited a constant number of times. Space O(rows × cols) in the worst case for the queue.

Recursive DFS is shorter, but Python's recursion limit (about 1,000) can be hit on a big island; BFS or an explicit stack avoids that.

Grid-graph variations: max area of an island, surrounded regions, rotting oranges (multi-source BFS: start the queue with all rotten oranges and count levels), and walls and gates.

Pattern: BFS finds the shortest path when every step costs the same, because it explores all cells at distance 1, then distance 2, and so on. The first time you reach the target, that's the shortest distance.

Time and space O(V + E): for a grid, O(rows × cols).

To return the path itself, store each cell's parent when you first reach it, then walk back from the goal.

When steps have different costs (road distances), BFS is no longer correct: use Dijkstra's algorithm. If costs are only 0 or 1, a "0-1 BFS" with a deque works.

Other BFS shortest-path problems: word ladder (each word is a node; neighbours differ by one letter), minimum knight moves, open-the-lock.

Courses and prerequisites form a directed graph (edge: prerequisite → course). All courses can be finished exactly when the graph has no cycle. A valid order is a topological sort.

Pattern: Kahn's algorithm. Count each course's prerequisites (its in-degree). Start with courses that have none; taking a course reduces the in-degree of the courses that depend on it. If some courses are never reached, there's a cycle.

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

A DFS version also works: mark nodes as "visiting" and "done"; reaching a "visiting" node means a cycle; adding nodes when they're done gives the reverse topological order.

Topological sort appears everywhere dependencies do: build systems (Make, Bazel), package installation order, task schedulers (Airflow DAGs), spreadsheet recalculation, and the alien dictionary problem.

Dijkstra's algorithm finds the cheapest path from a start node to all others when edge weights are non-negative.

Pattern: BFS with a priority queue (min-heap) instead of a plain queue: always expand the node with the smallest known distance. When a node is popped, its distance is final.

Time O((V + E) log V) with a binary heap.

Interview points:

• Negative weights break it (a later negative edge could make a "final" distance cheaper). Use Bellman-Ford (O(V·E)), which also detects negative cycles.
• The "skip outdated entries" check replaces a decrease-key operation, which Python's heapq doesn't have.
• A* search adds a heuristic (e.g. straight-line distance to the goal) to explore fewer nodes; it's what maps and games use.
• Typical problems: network delay time, cheapest flights with at most k stops (a variation that also tracks stops), path with minimum effort in a grid.

Union-Find keeps track of items split into groups and supports two fast operations:

• find(x): which group is x in (returns the group's representative, its "root");
• union(x, y): merge the groups of x and y.

With path compression and union by size, both are effectively O(1) (technically inverse Ackermann time).

Use it for:

• number of connected components as edges arrive one by one (a stream);
• cycle detection in an undirected graph ("redundant connection");
• Kruskal's minimum spanning tree: sort edges by weight, add each edge if it joins two different groups;
• grouping equivalent items: accounts merge, similar strings, "friend circles".

Compared with BFS/DFS: union-find shines when connections are added over time and you repeatedly ask "are these connected?". It can't easily handle edge removals.

A trie (prefix tree) stores strings character by character, so words with the same prefix share a path. Looking up a word or prefix takes O(length of the word), no matter how many words are stored.

Uses: autocomplete, spell checkers, IP routing (longest prefix match), word search in a grid (prune paths that aren't a prefix of any word), and replacing words with their roots.

Trade-off: tries can use a lot of memory (a node per character). Compressed tries (radix trees) merge single-child chains. For simple "is this word in the set?" checks, a plain set is simpler and faster.

Pattern: backtracking: build a solution step by step; at each step choose, explore further, then un-choose and try the next option.

For subsets, each element is either in or out: 2ⁿ subsets.

Time O(n · 2ⁿ) (2ⁿ subsets, each copied in O(n)); space O(n) for the recursion, plus the output.

Note current[:]: appending current itself would store the same list object every time, and all entries would end up empty after backtracking.

Iterative alternatives: start from [[]] and, for each number, add it to every existing subset; or use bitmasks (for mask in range(2**n)).

Pattern: backtracking where each position can take any unused element. There are n! permutations.

Time O(n · n!), space O(n) for the recursion.

With duplicates ([1, 1, 2]): sort first, and skip nums[i] if it equals nums[i - 1] and nums[i - 1] isn't currently used; that way identical values are always used in the same order.

The backtracking template fits many problems:

def backtrack(state):
    if is_complete(state):
        record(state)
        return
    for choice in choices(state):
        if is_valid(choice, state):
            make(choice)
            backtrack(state)
            undo(choice)

Problems: combinations, combination sum, letter combinations of a phone number, N-Queens, Sudoku solver, word search, generating valid parentheses. Pruning (stopping early when a partial solution can't work) is what makes backtracking fast in practice.

Pattern: backtracking with pruning. To avoid duplicates like [2, 3] and [3, 2], only pick candidates at or after the current index. Sorting lets you stop early once a candidate is too big.

Variations to know:

Complexity is exponential in the worst case. Talk about pruning, and mention that if the interviewer only needs the number of combinations, DP is the better tool.

Dynamic programming (DP) solves problems made of overlapping subproblems: the same smaller question gets asked many times. Solve each subproblem once and reuse the answer.

Climbing Stairs: you can climb 1 or 2 steps at a time. How many ways to reach step n?

To reach step n, your last move came from step n−1 or step n−2, so: ways(n) = ways(n - 1) + ways(n - 2), with ways(1) = 1, ways(2) = 2.

How to approach any DP problem:

1. Define the state: what does dp[i] mean? ("number of ways to reach step i")
2. Find the recurrence: how does dp[i] depend on smaller states?
3. Base cases.
4. Order: compute small states before the ones that need them (or use memoised recursion).
5. Optimise space if only the last few states are needed.

Clues that a problem is DP: "how many ways", "minimum/maximum cost or length", "is it possible", and choices at each step where greedy choices can fail.

Given coin values and an amount, return the minimum number of coins needed (unlimited coins of each value), or -1.

Why greedy fails: with coins [1, 3, 4] and amount 6, greedy takes 4 + 1 + 1 = 3 coins, but 3 + 3 = 2 coins.

DP state: dp[a] = the fewest coins to make amount a. For each amount, try every coin as the last coin: dp[a] = 1 + min(dp[a - coin]) over coins with coin <= a.

Time O(amount × number of coins), space O(amount).

This is the unbounded knapsack shape. The loop order in the "ways" version matters: coins outside means 1+2 and 2+1 are counted once; amounts outside would count orderings separately (that's the "climbing stairs with these step sizes" problem).

Find the length of the longest strictly increasing subsequence (not necessarily contiguous). In [10, 9, 2, 5, 3, 7, 101, 18], it's 4: [2, 3, 7, 18].

DP, O(n²): dp[i] = length of the longest increasing subsequence ending at index i = 1 + the best dp[j] for earlier j with a smaller value.

Faster, O(n log n): keep tails[k] = the smallest possible tail of an increasing subsequence of length k+1. For each number, binary-search where it fits: it either extends the longest run or replaces a tail with a smaller one (making future extensions easier).

Note: tails is not the subsequence itself, only the right length. To rebuild the actual subsequence, also store each element's predecessor.

Related problems: Russian doll envelopes (sort by width, then LIS on height), the maximum number of non-overlapping chains, and longest non-decreasing subsequence (use bisect_right).

Find the length of the longest sequence of characters that appears in order (not necessarily contiguously) in both strings. "abcde" and "ace" → 3 ("ace").

State: dp[i][j] = LCS of the first i characters of a and the first j of b.

• If a[i-1] == b[j-1]: dp[i][j] = dp[i-1][j-1] + 1 (use both characters).
• Otherwise: dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (drop one character from one string).

Time and space O(m × n). Space can drop to O(min(m, n)) by keeping only two rows (but then you can't walk back to recover the string).

The same 2D table pattern solves edit distance (minimum insertions, deletions and substitutions; used in spell checkers and diff tools), the longest common substring (contiguous: reset to 0 on a mismatch), and interleaving strings.

Houses in a row hold amounts of money; you can't rob two adjacent houses. What's the maximum total?

State: best[i] = the most you can get from the first i houses. For each house, either skip it (best[i-1]) or take it (its money + best[i-2]).

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

This "take it or skip it, with a constraint on neighbours" shape is very common: maximum sum of non-adjacent elements, delete-and-earn, scheduling jobs that can't overlap (weighted interval scheduling, which adds a binary search), and 0/1 knapsack (take or skip each item, subject to a weight limit).

For trees (House Robber III), the same idea runs as a DFS returning two values per node: the best total with and without robbing that node.

You have items with weights and values, and a bag with a weight limit. Each item can be taken at most once. Maximise the total value.

State: dp[w] = the best value achievable with capacity w, using the items considered so far. For each item, either skip it, or take it: value + dp[w - weight].

Iterate capacities backwards so each item is used at most once in this pass (going forwards would let it be reused, which is the unbounded knapsack).

Time O(n × capacity), space O(capacity). That's "pseudo-polynomial": fast when the capacity is a reasonable number, but the problem is NP-hard in general (with huge capacities).

Knapsack in disguise: partition equal subset sum, target sum with + and − signs, last stone weight II, and budget-limited selection problems.

Greedy by value/weight ratio is correct only for the fractional knapsack (where you can take part of an item).

A greedy algorithm makes the locally best choice at each step and never reconsiders. It's fast and simple, but only correct when you can argue that the local choice never hurts the final result. Always try to find a counterexample, or explain why there isn't one.

Jump Game: nums[i] is the maximum jump length from index i. Can you reach the last index?

Greedy idea: track the furthest index reachable so far. If you ever stand on an index beyond it, you're stuck.

Both are O(n) time, O(1) space. A DP solution would be O(n²).

Classic problems where greedy is correct:

• interval scheduling: pick the meeting that ends earliest, repeatedly, to fit the most meetings;
• gas station, assign cookies, minimum arrows to burst balloons, task scheduler;
• Huffman coding, Dijkstra (greedy on the closest node), Kruskal's and Prim's spanning trees.

Where greedy fails: coin change with arbitrary coins, 0/1 knapsack, longest path problems. Those need DP.

Integers are stored in binary, and bitwise operators work on all bits at once, in O(1).

Useful tricks:

Where bits appear: subsets as bitmasks (and bitmask DP, such as the travelling salesman problem with up to ~20 cities), permission flags, Bloom filters, compact boolean arrays, and hashing.

Python integers have unlimited size, so problems that assume 32-bit overflow (reverse bits, add without +) need masking with & 0xFFFFFFFF.