DSA patterns

Store each value's index, and before storing, look up target - x. Checking first stops a number pairing with itself.

Two strings are anagrams exactly when their character counts match. A 26-slot array or a Counter beats sorting: O(n) instead of O(n log n).

Every anagram of a word shares one key: its sorted letters, or a tuple of 26 counts. Map that key to a list of words.

Keep two maps, s-to-t and t-to-s, and fail on any conflict. One map alone accepts "ab" and "aa".

Keep each value's most recent index; a duplicate counts if i - last[x] <= k. This is a first taste of a sliding window.

Boyer-Moore voting: keep a candidate and a count, add one for a match and subtract one otherwise. The majority element survives because it outnumbers everything else combined.

A count can't exceed n, so put values into buckets indexed by count, then read buckets from the highest. That's O(n). A heap also works; it returns in the Heaps pattern.

One set per row, column and 3×3 box. The box index is (r // 3, c // 3). Alternatively, one set of tuples such as ("row", r, val).

Only start counting from a number whose predecessor isn't in the set. Each number is then visited at most twice, so the total is O(n).

Values are 1 to n, so value v can mark index v − 1, by making it negative. Indexes still positive at the end are the missing numbers.

Count every sum a + b in a map, then for every c + d look up −(c + d). O(n²) instead of O(n⁴).

The answer is in 1 to n + 1. Swap each value v in that range into index v − 1 until nothing moves (cyclic sort), then the first index i holding the wrong value gives i + 1.

Move each pointer past non-alphanumeric characters before comparing, and compare lowercase. No need to build a cleaned copy.

Sorted order tells you which pointer to move: too small means move lo right, too big means move hi left. O(1) space, unlike the map.

Write a value only when it differs from the last written one. Because the input is sorted, duplicates are always adjacent.

Compact the non-zeros to the front, then fill the rest with zeros. Or swap as you go, which keeps it a single pass.

The largest square is at one of the two ends. Compare the ends and write into the result from the back.

Fill nums1 from the end with the larger of the two current tails. Only leftover nums2 elements need copying at the end.

On the first mismatch, try skipping the left character or the right one and check the rest. Only one branch point is ever needed, so it's still O(n).

Sort, then for each i run converging pointers on the right side. Skip equal neighbours for both i and the pointers to avoid duplicate triplets.

Area is limited by the shorter line, so moving the taller one can never help. Always move the shorter side.

Keep low, mid and high. A 0 swaps to low, a 2 swaps to high, a 1 stays. Don't advance mid after swapping with high; the incoming value is unchecked.

Sort, then pair the heaviest person with the lightest if they fit; otherwise the heaviest goes alone. The heaviest person must leave on some boat, so pairing them with the lightest is never worse.

Water above a bar is min(max_left, max_right) − height. Move the side with the smaller running max: its water level is already decided by that max.

Keep the lowest price seen so far; each day's best profit is today's price minus that minimum. One pass, O(1) space.

Keep a running sum: add the entering element and subtract the leaving one. Compare sums, not averages, since k is constant.

Grow the right edge; when the new character is already in the window, move the left edge past its previous position. Storing each character's last index lets the left edge jump directly.

Grow until the sum reaches the target, then shrink from the left while it still does, recording the length each time. This relies on all numbers being positive.

Count zeros in the window and shrink while the count exceeds k. The longest window seen is the answer; you never actually flip anything.

Keep a count map of the window. When it holds more than two keys, shrink from the left and delete keys whose count reaches zero.

A window is fixable when length − count of its most frequent letter ≤ k. You don't need to decrease the stored maximum when shrinking: a stale maximum can only keep the window from growing, never produce a wrong longer answer.

Slide a window of length len(s1) over s2 and compare letter counts. Tracking how many of the 26 counts currently match makes each step O(1).

Taking k cards from the ends leaves a contiguous block of n − k in the middle. Maximise your points by minimising that middle window's sum.

After sorting, try making every element in a window equal to its largest. The cost is largest × length − window sum; shrink while it exceeds k.

"Exactly K distinct" isn't monotonic, but "at most K" is. Count windows with at most K and subtract those with at most K − 1. At most K adds right − left + 1 per step.

Track how many required characters are fully satisfied (have versus need). When all are, shrink from the left to minimise, updating the count as characters leave.

Build the prefix array once in O(n); each query is prefix[right + 1] − prefix[left]. The extra leading zero removes an edge case.

Keep a running left sum; the right sum is total − left − nums[i]. The pivot is where they're equal.

The answer at i is (product of everything left of i) × (product of everything right of i). Fill left products forward, then multiply in right products backward, with no division.

The best subarray ending at j is prefix[j] − smallest earlier prefix, the same shape as Best Time to Buy and Sell Stock. Kadane's version: keep the best sum ending here, restarting when it goes negative.

Count how many earlier prefixes equal running − k. Start the map with {0: 1} so subarrays that begin at index 0 count.

Treat 0 as −1, so an equal number of 0s and 1s means a zero sum. Store the first index of each prefix sum; the longest span between equal prefixes is the answer.

Two prefixes with the same remainder mod k bound a subarray divisible by k. Count remainders. Python's % already returns a non-negative result for negative numbers; many other languages need a fix.

P[r][c] holds the sum of the rectangle above-left. A query adds the big rectangle, subtracts the two strips, and adds back the overlapping corner.

For each booking add seats at first − 1 and subtract at last; one prefix sum at the end gives every flight's total. O(n + bookings) instead of O(n × bookings).

Fix a pair of rows; the column sums between them form a 1-D array. Count its subarrays summing to the target with the prefix-map trick. O(rows² × cols).

With the half-open template, search for the first index with nums[i] ≥ target, then check whether it holds the target.

The insert position is the first index with nums[i] ≥ target, which is exactly what the template returns, including len(nums) when every value is smaller.

First position: first index with value ≥ target. Last position: (first index with value > target) − 1. The same as bisect_left and bisect_right.

Search indexes 0 to m × n − 1, and map index i to matrix[i // n][i % n].

Compare nums[mid] with the last element. Everything at or before the minimum's position is greater than the last element; everything after is not. That's a False-then-True condition.

At each step one half is in order. If the target lies within that half's range, search it; otherwise search the other. Or find the minimum first, then binary search the right piece.

If nums[mid] < nums[mid + 1], you're on an upward slope, so a peak exists to the right. Otherwise one exists at mid or to the left.

Timestamps arrive in increasing order, so each key's list stays sorted. get is bisect_right(times, t) − 1, the last time ≤ t.

Search speeds from 1 to max(piles). A speed is feasible if sum(ceil(p / speed)) ≤ h. Faster is always at least as feasible, so the condition flips once.

Search capacities from max(weights) to sum(weights). To check a capacity, fill each day greedily in order and count the days needed.

Sort positions. "Can I place m balls at least d apart?" is True for small d and False for large d. Place greedily from the left, and search for the largest d that's still True.

It's Capacity To Ship with days renamed to subarrays: the smallest maximum sum for which a greedy split needs at most k pieces.

For a candidate value x, count entries ≤ x by walking a staircase from the bottom-left in O(n). The answer is the smallest x whose count is ≥ k. A heap also works; compare both.

Binary search how many elements to take from the shorter array. A partition is right when both left maxima are ≤ both right minima. Use ±infinity at the edges.

Walk the list with prev and cur. Save cur.next, point cur.next at prev, then advance both. Also write the recursive version once.

Build from a dummy node, always attaching the smaller head. When one list runs out, attach the rest of the other in one step.

Fast moves two steps, slow one. With a cycle, fast gains one node per step and must land on slow; without one, fast hits None.

When fast reaches the end, slow is at the middle. With an even length, the loop condition decides which of the two middles you get; know which yours returns.

Move the lead pointer n steps ahead of the trailing one, then move both until lead reaches the last node. Trail now sits just before the node to delete.

Walk both pointers; when one reaches the end, restart it at the other list's head. Both then travel a + b steps and meet at the intersection, or both reach None together.

After slow and fast meet, move one pointer back to the head and advance both one step at a time. They meet at the cycle's start; the distances work out exactly.

Loop while either list or the carry remains, treating a missing node as 0. Build the result from a dummy node.

Find the middle with fast and slow, reverse the second half, then interleave the two halves. Cut the list at the middle, or the result loops.

Treat each index i as a node pointing to nums[i]. A duplicate value means two nodes point to the same place, which forms a cycle whose start is the duplicate.

First pass: map each old node to a new copy. Second pass: set each copy's next and random through the map. An O(1)-space version interleaves copies into the original list.

For each group, check k nodes remain, reverse exactly those, then connect the previous group's tail to the new head. A dummy head makes the first group behave like the rest.

Push opening brackets; on a closing bracket, the stack top must be its partner. The string is valid only if the stack is empty at the end.

Store the minimum so far with every push, as a pair, or in a second stack. getMin is then the top's stored minimum.

Push numbers; for an operator, pop two, apply it, and push the result. Pop order matters for − and ÷, and division must truncate toward zero: use int(a / b), not //.

Push into an in-stack; pop from an out-stack, refilling it from the in-stack only when it's empty. Each item moves at most twice, so operations are O(1) on average.

Keep a stack of indexes with decreasing temperatures. A warmer day pops every colder index and records the distance i − popped.

Loop over indexes 0 to 2n − 1 using i % n, but only push during the first pass. The second pass gives earlier items a chance to see values that wrap around.

Store (price, span) pairs. A new price pops all smaller-or-equal prices and absorbs their spans.

While k > 0 and the stack top is larger than the next digit, pop it: a smaller digit earlier always wins. Remove any remaining k from the end, then strip leading zeros.

On [, push the current string and repeat count, then start fresh. On ], pop and set current = saved + count × current. Multi-digit counts need accumulating.

Only a left-moving asteroid meeting a right-moving stack top collides. Pop smaller ones, destroy both on a tie, and push the new one only if it survives.

Sort cars by position, closest to the target first, and compute each arrival time. A car catches the fleet ahead if its time is ≤ that fleet's time; otherwise it starts a new fleet.

Keep indexes in a deque with decreasing values. Pop smaller values from the back before pushing; pop the front when it leaves the window. The front is always the window maximum.

Keep an increasing stack of indexes. When a shorter bar arrives, pop taller bars: each popped bar's rectangle extends from the new stack top + 1 to the current index − 1. A final height of 0 flushes the stack.

Keep a deque of prefix indexes with increasing prefix sums. Pop from the front while the current prefix minus the front's is ≥ k (recording lengths), and from the back while the back's prefix is ≥ the current one.

Sort by start. If an interval starts at or before the last merged interval's end, extend that end with max; otherwise start a new merged interval.

Copy intervals that end before the new one starts, merge every interval that overlaps it into one, then copy the rest.

Sort by end and keep an interval whenever it starts at or after the last kept end. Finishing earliest leaves the most room; the answer is the number you didn't keep.

The overlap of the current pair is [max(starts), min(ends)] if non-empty. Then advance whichever interval ends first.

Sort by start ascending and end descending. Then an interval is covered exactly when its end is ≤ the largest end seen so far.

A booking conflicts with an existing one when start < other_end and other_start < end. A list check is O(n) per booking; a sorted list with bisect checks only the neighbours.

Add passengers at each pickup and remove them at drop-off. Process events in order (drop-offs first at the same stop) and fail if the load ever exceeds capacity. Locations are small, so a difference array also works.

The answer is the most intervals active at once. These intervals are closed, so a start equal to an end still overlaps; sweep with the end event at end + 1, or sort starts and use a min-heap of ends.

Sort intervals by start and queries by value. For each query, push intervals that have started (keyed by size), pop those that have ended, and the heap top is the smallest interval containing it.

xⁿ = (x^n/2)², times x when n is odd, which makes it O(log n). For negative n, compute 1 / x⁻ⁿ.

There are 2ⁿ subsets. Either branch on include or exclude for each element, or loop from start and record the path at every call; every node of that recursion tree is a subset.

Track used elements with a boolean list (or swap elements in place). There are n! results, and each costs O(n) to copy.

Recurse with the same index i rather than i + 1 so a number can repeat. Sort first, and break out of the loop once a number exceeds the remaining target.

Sort, then skip a value equal to the previous one at the same level: i > start and nums[i] == nums[i − 1]. Equal values may appear down one path, but never as two siblings.

Move to i + 1 so each number is used once, and skip equal siblings as in Subsets II.

Sort, then skip nums[i] when it equals nums[i − 1] and that previous copy isn't currently used. This forces equal values into a fixed order, so each arrangement appears once.

One recursion level per digit and one branch per letter it maps to. An empty input returns an empty list, not a list holding an empty string.

Add ( while fewer than n are open, and ) only while fewer closes than opens have been placed. Every complete path is then valid; nothing needs filtering.

From position start, try each end index and recurse only when that piece is a palindrome. A precomputed palindrome table avoids re-checking the same substrings.

DFS from every cell, marking the current cell as used (overwrite it temporarily) and restoring it on the way back. Prune by checking the board has enough of each letter before searching.

Each bucket must reach sum / k. Place numbers largest first so failures appear early, and skip a bucket whose current sum equals one already tried for this number; it would lead to the same result.

Split at every operator, solve the left and right sides recursively, and combine every pair of results. Memoise on the substring, because the same pieces recur.

Place one queen per row. Keep sets of used columns and both diagonals; a cell's diagonals are r − c and r + c, so every check is O(1).

Keep row, column and box sets; try digits in an empty cell and undo on failure. Filling the empty cell with the fewest options first cuts the search dramatically.

Depth is 1 + the deeper child's depth, and 0 for an empty tree. Solve it with BFS too, counting levels.

Swap each node's children, then invert both subtrees. Any traversal order works as long as every node is visited once.

Two trees match when both are empty, or both roots are equal and both pairs of subtrees match. Handle the "one is empty" case before reading values.

Record len(queue) before the inner loop and pop exactly that many nodes. That boundary is what separates one level from the next.

The longest path through a node is left height + right height. Return the height to the parent, but update a global diameter at every node; the answer may not pass through the root.

Return the height, or −1 once any subtree is unbalanced, and propagate the −1 upward. One O(n) pass instead of recomputing heights at every node in O(n²).

Compare the two subtrees as mirrors: left.left against right.right, and left.right against right.left.

At each node of the main tree, run Same Tree against the smaller tree. O(m × n) is accepted; serialising both trees and matching strings brings it down to O(m + n).

Pass down the largest value seen on the path from the root. A node is good when its value is ≥ that maximum.

Carry the path and the remaining sum down. At a leaf with remaining 0, save a copy of the path. Pop the node after both recursive calls.

If the node is p or q, return it. Otherwise search both sides: if both return a node, this is the LCA; if only one does, pass that result up.

Take the last node of each level. Alternatively, a DFS visiting right before left can record the first node seen at each new depth.

Number nodes as in a heap: the children of i are 2i and 2i + 1. A level's width is the last index − the first + 1. Python's integers don't overflow, but re-basing indexes each level keeps them small.

Pass down the allowed range (low, high). Comparing a node only with its children misses violations further down. Equivalently, an in-order traversal must be strictly increasing.

Traverse in order and stop at the k-th node. An iterative in-order with an explicit stack makes stopping early natural.

If both values are smaller, go left; if both are larger, go right. Otherwise this node separates them and is the LCA. O(h), with no need to search both sides.

Make the middle element the root so both sides are the same size, and build each half recursively.

With zero or one child, replace the node with that child. With two, copy in the smallest value from the right subtree, then delete that value from the right subtree.

Push the left spine. On next(), pop a node and push the left spine of its right child. Every node is pushed once, so each call is O(1) on average.

The next preorder value is the root; its position in the inorder list splits the left and right subtrees. Map values to inorder indexes first so each split is O(1).

It's Subarray Sum Equals K on every root-to-node path. Keep a count map of prefix sums during the DFS, and decrement the current sum when leaving a node.

Each node returns its value plus the better of its children's downward paths, ignoring negative ones with max(0, …). The global answer considers the node plus both children.

Record each node's parent with one DFS, so you can move up as well as down. Then BFS k steps from the target, with a visited set.

A preorder traversal with a marker for missing children describes the tree completely. Deserialise by reading tokens in the same order from an iterator.

Keep a min-heap of exactly k elements; its top is the k-th largest. Each add is O(log k).

Push negated weights. Pop the two heaviest and push back their difference if it isn't zero.

Keep a max-heap of size k by pushing negated distances. Compare squared distances; the square root never changes the order.

A size-k heap is O(n log k). Quickselect partitions like quicksort but recurses into one side only: O(n) on average, O(n²) in the worst case unless the pivot is random.

Order by (−count, word). A size-k heap would need both keys inverted, which is awkward in Python; heapq.nsmallest(k, words, key=lambda w: (−count[w], w)) expresses it directly.

The most frequent task sets the frame: (max_count − 1) × (n + 1) + tasks_with_max_count. If that's less than the number of tasks, the answer is the number of tasks. Simulating with a heap gives the same result.

Always place the most frequent character that isn't the one just placed: pop it, and push the previous character back only after this step. It's impossible exactly when some count exceeds (len + 1) // 2.

Push each list's head as (value, list index, node); the index breaks ties because nodes can't be compared. Pop the smallest, attach it, push its next. O(N log k).

Keep the lower half in a max-heap and the upper half in a min-heap, with sizes differing by at most one. The median is the larger heap's top, or the average of both tops.

Start with pairs (i, 0) for the first k values of i. Popping (i, j) pushes (i, j + 1). You never look at more than about k pairs.

Sort projects by capital. Each round, push the profits of every project now affordable into a max-heap, then take the most profitable. Taking the best affordable project is always safe.

Keep one element from each list in a min-heap and track the current maximum. [heap top, maximum] covers every list; advance the list holding the minimum, and stop when any list runs out.

Add each edge in both directions, then search from the source until you reach the destination. With up to 2 × 10⁵ nodes, use BFS or an iterative DFS; recursion would hit Python's limit.

Scan every cell; each unvisited land cell starts a new island, and a search marks all the land connected to it. The answer is the number of searches started.

Map each original node to its copy. Create the copy the first time you see a node, and connect neighbours through the map; the map also works as the visited set.

The same traversal as Number of Islands, but each search returns how many cells it covered. Take the maximum.

Put every rotten orange in the queue at the start. Each BFS level is one minute; if fresh oranges remain when the queue empties, return −1.

Rather than a BFS from every 1 to its nearest 0, run one BFS from all 0s together. A cell's first visit gives its distance.

Start from each ocean's border and move to neighbours of equal or greater height. Cells reached from both oceans are the answer.

Only regions touching the border survive. Mark every O connected to the border first, then turn the remaining Os into X and restore the marked ones.

Colour each node and give its neighbours the opposite colour; a neighbour with the same colour means it isn't bipartite. Start from every uncoloured node, since the graph may be disconnected.

BFS gives shortest paths when every step costs the same. Neighbours include diagonals, and check that the start and end cells are open before searching.

Each combination has eight neighbours, one wheel turned up or down. BFS from "0000", treating deadends as already visited.

Find one island with DFS and put all its cells in the queue. Then BFS outward over water; the first time you touch the other island, the level is the answer.

Neighbours differ by one letter. Bucket words by wildcard patterns such as h*t, so finding neighbours means looking up L patterns rather than comparing with every word.

The state is (row, column, keys held), with keys as a bitmask. The same cell with different keys is a different node; you're done when the mask has every key.

You can finish every course exactly when the prerequisite graph has no cycle. Run Kahn's algorithm and check whether it places every course. A three-colour DFS works too.

Kahn's order is a valid answer. Watch the direction: [a, b] means b comes before a, so the edge is b → a.

A node is safe when every path from it ends at a terminal node. Reverse the edges and run Kahn's from the terminal nodes; every node it removes is safe. A three-colour DFS also works: anything that reaches a cycle is unsafe.

The best roots are the tree's centre, one or two nodes. Remove all current leaves layer by layer until at most two nodes remain.

Process courses in topological order. A course finishes at its own time plus the latest finish among its prerequisites; the answer is the largest finish time.

Moving to a strictly larger neighbour can never loop, so the grid is a DAG. DFS with memoisation gives each cell's longest path in O(rows × cols) overall; peeling cells in topological order also works.

Union every connected pair; the number of distinct roots is the answer. Solve it with DFS too and compare: union-find wins when edges arrive over time.

Add edges in order. The first edge whose endpoints already share a root would close a cycle, so it's the answer.

You need at least n − 1 cables. If you have enough, the answer is the number of components minus one, since each spare cable joins two components.

Union every == pair first, then check each != pair: it fails if both sides share a root. Processing both kinds together in input order gives wrong answers.

Union every email in an account with that account's first email. Then group emails by root, sort each group, and put the owner's name in front.

Indexes linked by swaps, directly or through others, form a group whose characters can be arranged in any order. Sort each group's characters and place them into its sorted indexes.

Each equation a / b = k is a weighted edge in both directions (k and 1/k). Answer a query by searching for a path and multiplying weights, or use a weighted union-find that stores each node's ratio to its root.

Run Dijkstra from k. The answer is the largest shortest distance, or −1 if any node is unreachable.

Every pair of points is an edge, so the graph is dense. Prim's with a simple O(n²) scan suits dense graphs; Kruskal's sorts all edges and unions with a DSU. Know one well.

Relax with max(current effort, step) instead of adding. It still works because a path's cost never decreases as it grows.

A cheaper path with too many stops can block a pricier valid one. Run Bellman-Ford for k + 1 rounds, relaxing from a copy of the previous round's distances so each round adds at most one edge.

With n ≤ 100, Floyd–Warshall is simplest: three nested loops with the intermediate node outermost. Then count cities within the threshold, breaking ties by the larger index.

Moving into an empty cell costs 0 and into an obstacle costs 1. Use a deque: push 0-cost moves to the front and 1-cost moves to the back. O(rows × cols).

A path costs its highest cell, so minimax Dijkstra solves it. So does binary searching the time with a BFS check, or adding cells in height order with union-find until the corners connect.

Keep a count per node. A strictly shorter path replaces the count; an equally short one adds to it. Take counts modulo 10⁹ + 7.

Sort both lists and give each child the smallest cookie that satisfies them. Using a bigger cookie than needed can only hurt a later child.

Keep the farthest index reachable so far. If you ever stand beyond it, you're stuck; if it reaches the last index, you're done. O(n), where DP would be O(n²).

With unlimited transactions, the answer is the sum of every positive day-to-day increase. Each rise can be captured by buying before it and selling after.

Indexes reachable with j jumps form a range. Scan the current range while tracking the farthest next reach; each time you finish a range, count a jump.

A solution exists if total gas ≥ total cost. Scan with a running tank; when it drops below zero, no start from the current candidate up to here can work, so the next start is the station after.

Record each letter's last index. Extend the current part's end to the last index of every letter you pass; when you reach that end, close the part.

The smallest remaining card can only start a group, never sit inside one. Repeatedly start a group there and consume the next group-size values from the counts.

Keep the range [low, high] of possible open counts. ( raises both, ) lowers both, * lowers low and raises high. Fail if high goes negative, keep low at least 0, and succeed if low is 0 at the end.

Imagine sending everyone to A, then moving n people to B. Move the ones with the smallest costB − costA. Sorting by that difference is the whole solution.

Put a before b when a + b > b + a as strings; use functools.cmp_to_key. If the result starts with 0, the answer is "0".

Left to right: give one more than the left neighbour when rated higher. Right to left: do the same against the right neighbour, keeping the larger of the two values. Sum the result.

Drive as far as fuel allows, pushing every station you pass into a max-heap. When you can't reach the next point, refuel from the biggest station passed so far. Each refuel is one stop.

Ways to reach step n = ways to reach n − 1 + ways to reach n − 2. It's Fibonacci, so two variables are enough.

The cost to reach step i is the cheaper of arriving from i − 1 or i − 2, plus that step's cost. The top is one position past the last index.

f(i) = max(nums[i] + f(i + 2), f(i + 1)): rob this house and skip the next, or skip this one. Two rolling variables give O(1) space.

The first and last houses are neighbours, so they can't both be robbed. Run House Robber without the first house and without the last, and take the better. With one house, return it.

Taking value x earns x × count(x) and removes x − 1 and x + 1. Build points[x] and run House Robber over the values.

f(i) gets f(i + 1) if s[i] isn't '0', plus f(i + 2) if s[i:i+2] is between 10 and 26. A '0' can never start a code.

can(i) is true if some dictionary word matches at i and can(i + len(word)) is true. Memoise on i, and use a set of words.

A negative number turns the largest product into the smallest. Track both the maximum and minimum product ending here; the new maximum is the largest of x, x × old max, and x × old min.

cost(i) for the i-th travel day is the cheapest pass price plus the cost from the first travel day that pass doesn't cover. Iterate travel days rather than all 365.

f(i) = max(points[i] + f(i + brainpower[i] + 1), f(i + 1)). Going backward means every value you need is already computed.

The best subarray either doesn't wrap (normal Kadane) or wraps, which equals total − the minimum subarray. If every number is negative, the wrap case would be empty, so return the normal maximum.

Memoise on the start index and return every sentence for the rest of the string. The output can be exponential, so this is the best possible.

Half the total must be reachable as a subset sum. Iterate the capacity downward so each number is used once. A Python integer used as a bitset (bits |= bits << x) is a neat shortcut.

dp[a] = min(dp[a − coin] + 1) over coins, with dp[0] = 0 and infinity for unreachable amounts. For a minimum, loop order doesn't change the answer.

Put coins in the outer loop and amounts in the inner loop. Each combination is then built in one fixed coin order, so it's counted once.

The + numbers P and − numbers N satisfy P − N = target and P + N = total, so P = (target + total) / 2. Count subsets summing to P. Check parity and bounds first.

1 + 2 and 2 + 1 count separately, so put the target in the outer loop and numbers in the inner loop, the reverse of Coin Change II.

The squares are the coins: dp[n] = 1 + min(dp[n − k²]). A number theory result bounds the answer at 4, but the DP is what's being taught.

Every smashing order ends up splitting stones into two piles and taking the difference. Find the subset sum closest to half the total.

Each string costs some zeros and some ones. dp[z][o] is the most strings within those budgets; loop both capacities downward.

paths(r, c) = paths(r − 1, c) + paths(r, c − 1), with the first row and column all 1. One row of storage is enough.

If the characters match, extend the diagonal by one; otherwise take the better of dropping a character from either string.

Each cell adds its value to the smaller of the cell above and the cell to the left. One row, or the grid itself if you may modify it, is enough.

For a '1' cell, the largest square ending there has side 1 + min(top, left, top-left). The answer is the largest side, squared.

If the characters match, copy the diagonal. Otherwise take 1 + the minimum of insert (left), delete (up), and replace (diagonal). Converting to or from an empty prefix costs its length.

Expand around each of the 2n − 1 centres (characters and gaps) while the ends match. O(n²) time with O(1) memory; the DP table is also O(n²) but uses O(n²) memory.

Expand from every centre and count each successful step. Every palindrome is found exactly once, from its own centre.

dp[i][j] says whether s3[:i + j] can come from s1[:i] and s2[:j]. It's true if the last character matches s1 and dp[i − 1][j] holds, or matches s2 and dp[i][j − 1] holds. Check lengths first.

dp[i][j] counts ways to form t[:j] from s[:i]. Always inherit dp[i − 1][j] (skip this character of s); when the characters match, also add dp[i − 1][j − 1]. An empty t can be formed exactly once.

dp[i][j] says whether s[:i] matches p[:j]. A * either uses zero of the previous element (dp[i][j − 2]) or one more of it, if that element matches s[i − 1] (dp[i − 1][j]). Top-down memoisation on (i, j) is often easier to get right.

O(n²): lis[i] = 1 + max(lis[j]) over earlier smaller values. O(n log n): keep the smallest tail for each length and update it with bisect_left.

Keep three states per day: holding, just sold, and resting without stock. Update each from yesterday's states (you can only buy from resting); the answer is the best state without stock.

Each node returns (best if robbed, best if not). Robbed = value + both children's not-robbed; not robbed = each child's better option, summed. One post-order pass.

Sort by width ascending and height descending, then take the LIS of heights. The descending heights stop two envelopes of equal width from nesting.

Sort words by length. A word's chain is 1 + the best chain of any word formed by deleting one of its letters; a dictionary keyed by word makes each lookup O(1).

Keep buy[j] and sell[j] for j = 1 to k, where buy[j] builds on sell[j − 1]. If k ≥ n / 2, the limit never binds and it's the unlimited case.

Let diff(i, j) be the best score margin the player to move can force on nums[i..j]: max(nums[i] − diff(i + 1, j), nums[j] − diff(i, j − 1)). Player 1 wins if diff(0, n − 1) ≥ 0.

Pad with 1s at both ends. If k is the last balloon burst strictly between i and j, its neighbours are then i and j: dp[i][j] = max(dp[i][k] + dp[k][j] + nums[i] × nums[k] × nums[j]).

Each node reports whether it needs covering, has a camera, or is covered without one. Working up from the leaves, a parent of an uncovered child must hold a camera; handle an uncovered root at the end. Store the root's state first: count + (dfs(root) == NEEDS_COVER) reads count before the DFS has updated it.

With at most 14 tasks, store for each mask of finished tasks the best (sessions used, time used in the current session), compared as a pair. Adding task t either fits in the current session or opens a new one.

Each node maps characters to children and marks whether a word ends there. search needs the end flag; startsWith only needs the path to exist.

A . tries every child: DFS from that node over the rest of the pattern. Without dots it's a plain lookup.

Insert every root. For each word, walk the trie and stop at the first node that ends a root; replace the word with that prefix, or keep it if none is found.

Walk the trie as each character is typed. Inserting words in sorted order and keeping up to three at every node makes each query O(1) after the walk. Sorting plus binary search is an equally good approach.

Put every word in one trie and DFS the board once, following trie edges. Remove words once found and prune empty nodes, or the search repeats work and times out.

Insert each number bit by bit, from the highest bit down. For each number, walk toward the opposite bit at every level when possible; that maximises the XOR from the top bit down.

a ^ a = 0 and a ^ 0 = a, so XORing every number cancels the pairs and leaves the single one. O(1) space.

n & (n − 1) removes the lowest set bit; count how many times until n is 0. n.bit_count() does it in one call.

bits[i] = bits[i >> 1] + (i & 1): drop the last bit, which you've already counted, then add it back. O(n) overall.

XOR every index 0 to n with every value; present numbers cancel, leaving the missing one. The sum formula n(n + 1) / 2 − total works too.

Take the lowest bit of n 32 times, shifting each onto the result. Python integers are unbounded, so loop exactly 32 times.

For each of the 32 bits, count how many numbers have it set; counts that aren't a multiple of 3 belong to the single number. Convert from 32-bit two's complement if the result is negative.

a ^ b adds without carrying and (a & b) << 1 is the carry; repeat until the carry is 0. In Python, mask with 0xFFFFFFFF each round or negative inputs loop forever, then convert back to a signed value.

Rotating 90° clockwise equals transposing (swapping across the main diagonal) then reversing each row. Both steps are in place.

Keep top, bottom, left and right boundaries. Walk a side, then shrink its boundary; before walking back along the opposite side, check the boundaries haven't crossed.

Use the first row and column to record which rows and columns to clear, plus one flag for whether the first column itself had a zero. Clear from the bottom-right so markers aren't overwritten early.

Replacing a number with the sum of its digit squares either reaches 1 or loops forever. Detect the loop with a set, or with fast and slow pointers.

For each prime p, mark multiples from p² onward as composite. O(n log log n). Count primes strictly less than n.

Digits i and j (counted from the left) contribute to position i + j + 1 of the result. Accumulate every product into an array, then carry, then strip leading zeros.

A hash map for O(1) lookup and a doubly linked list for recency: move a node to the front on each access and evict from the back. OrderedDict gives the same behaviour in a few lines.

Keep values in a list and each value's index in a map. To remove, move the last element into the removed slot, update its index, and pop the end. random.choice is O(1).

Keep each index's history as (snapshot id, value) pairs, appending only when set. get is a binary search for the last entry at or before the requested snapshot.

Store tweets per user with a global timestamp and followees in sets. A feed merges the most recent tweets of the user and followees with a heap, stopping at 10.

Map key → (value, frequency) and frequency → an OrderedDict of keys. Track the minimum frequency: evict the oldest key at that frequency, and a newly inserted key resets the minimum to 1.

A Fenwick tree gives point updates and prefix sums in O(log n) in a few lines. Keep the current values separately so an update becomes a delta. A segment tree does the same and extends to range minimum or maximum.

str.find is the practical answer. For KMP, compute the prefix function of pattern + "#" + text; a value equal to len(pattern) marks where a match ends. O(n + m).

Process from the right. Map values to ranks, then for each value count already-seen smaller ranks with a prefix query and add it. A merge sort that counts elements jumping past each one also works.

In merge sort, before merging two sorted halves, count pairs with nums[i] > 2 × nums[j] using two pointers. The sorted halves make the count linear per merge, so O(n log n) overall.

Slide a length-10 window and keep seen substrings in a set; record one the second time it appears. A rolling hash, or 2 bits per letter, makes each step O(1).

The longest prefix that is also a suffix is exactly the last value of the prefix function.

Only the part after the longest palindromic prefix needs mirroring in front. Its length is the last prefix-function value of s + "#" + reversed(s).

If a duplicate of length L exists, one of length L − 1 does too, so binary search the length. Check a length by rolling-hashing every window; on a hash match, compare the actual strings to rule out collisions.