Name the pattern

The tells, on one screen

Each line is a detail in the problem statement and the tool it usually points to. "Usually" is doing work: every one of these has a variation that breaks it, and the questions below end on that variation.

Sorted input, or you are allowed to sort

Two pointers for pairs and triples; binary search for a single target or a boundary.

"Have I seen this before?" or "how many of each?"

Hash map or hash set. It turns an O(n) look-back into an O(1) lookup.

Contiguous run plus a condition that only gets worse as it grows

Sliding window. Negative numbers break the "only gets worse" part; switch to prefix sums and a hash map.

Next greater, next smaller, or the nearest bar that blocks

Monotonic stack. Each element is pushed once and popped once, so O(n) overall.

Matching pairs, nesting, undo

Stack.

"Find the smallest X such that it works" and checking one X is easy

Binary search on the answer. The check must be monotonic: if X works, every bigger X works.

Top k, kth largest, a running median, merge k sorted things

Heap. A heap of size k gives O(n log k).

Every subset, every arrangement, place pieces under rules

Backtracking. Choose, recurse, un-choose; prune as early as the rules allow.

Grid or network, fewest steps, every edge costs the same

BFS. Weighted edges mean Dijkstra; negative edges mean Bellman-Ford.

Prerequisites, "must come before", build order

Topological sort, which also detects the cycle that makes an order impossible.

Groups that merge, "are these two connected?" as edges arrive

Union-find.

Many strings sharing prefixes

Trie.

Count the ways, or the best score, and choices overlap

Dynamic programming. One index: 1-D. Two strings or a grid: 2-D.

A local choice you can prove never hurts

Greedy. Try to break it with a small counterexample before trusting it.

Start and end times

Intervals: sort by start to merge, sort by end to keep the most, sweep the endpoints to count overlaps.

Everything appears twice except one, or O(1) space on integers

Bits. XOR cancels pairs.

Questions

Answer each one yourself before you open it.

1. 01Given an unsorted list of numbers and a target, return the positions of the two numbers that add up to the target.

   Hash map. The tell: for each number you need to ask "have I already seen the one number that completes it?", and that is a lookup, not a search.

   Walk once, and for each value check whether target minus value is already in the map from value to index; if not, store the current one. That is O(n) time and O(n) space, against O(n^2) for checking every pair.

   Follow-up Now the list is sorted and you must use O(1) extra space.

   Two pointers from both ends. If the sum is too small, move the left pointer right; too big, move the right pointer left. Still O(n), and no map.

   Learn more Clinic #05 - Two Sum · O(1) yaad (hashing lab)

2. 02You have a list of words. Put the words that are rearrangements of each other's letters into the same group.

   Hash map keyed by a canonical form. The tell: "the same up to reordering" means you need a key that ignores order.

   Two words are rearrangements exactly when their sorted letters match, so use the sorted word (or a 26-slot letter count) as the map key and append each word to its bucket. Sorting keys costs O(n k log k) for n words of length k; the count key is O(n k). Comparing every pair of words would be O(n^2 k).

   Follow-up The words can contain any Unicode character, not just a to z.

   The fixed 26-slot count no longer fits. Use the sorted string, or a count map serialised in a fixed key order, as the key. The pattern is unchanged; only the key changes.

   Learn more Hashing

3. 03Given an unsorted list of integers, find the length of the longest run of consecutive values, like 4, 5, 6, 7, in O(n) time.

   Hash set, and only start counting at the beginning of a run. The tell: "O(n)" rules out sorting, and "consecutive values" means you only ever ask "is x+1 present?".

   Put every number in a set. For each x, start counting only if x-1 is not in the set, then walk x+1, x+2 while they exist. Each number is visited at most twice in total, so it is O(n); sorting first would be O(n log n).

   Follow-up Why is it still O(n) when there is a while loop inside the for loop?

   Because the inner walk only runs from the start of a run, and each number belongs to exactly one run. Across the whole loop the inner steps add up to n, not n per element. That amortised argument is the answer they want.

   Learn more Hashing

4. 04Given a list of numbers in no particular order, return every distinct triple that sums to zero.

   Sort, fix one, converge two pointers on the rest. The tell: a sum of a fixed small number of elements, and nothing stops you sorting first.

   For each index i, run the two-pointer pair search on the part to its right looking for -nums[i], skipping equal values to avoid duplicate triples. That is O(n^2) against O(n^3) for three nested loops, and the sort is only O(n log n) on top.

   Follow-up Now return the triple whose sum is closest to a target, not equal to it.

   Same pattern. Track the best distance seen as the pointers converge, moving whichever pointer brings the sum toward the target. Still O(n^2).

   Learn more Clinic #18 - 3Sum · Arrays & Strings

5. 05You have a row of vertical walls of different heights. Pick two walls so the water held between them, width times the shorter wall, is as large as possible.

   Two pointers converging from the ends. The tell: the answer depends on a pair, and starting wide lets you prove which side can never do better.

   Start at both ends, the widest possible container. Moving the taller wall inward can only shrink the width without raising the shorter side, so always move the shorter one. Each step discards one wall for good, giving O(n) against O(n^2) for every pair.

   Follow-up Now the water is what sits on top of every bar in the row after rain, summed.

   That is a different problem: each bar holds min(tallest to its left, tallest to its right) minus its own height. Prefix and suffix maxima give O(n) with O(n) space, and two pointers tracking the running max from each side get it to O(1) space.

   Learn more Clinic #17 - Container With Most Water

6. 06Find the length of the longest stretch of a string that has no repeated character.

   Sliding window. The tell: a contiguous stretch, plus a condition (no repeats) that can only break by adding a character and only heal by removing one.

   Grow the right edge; when the new character is already in the window, move the left edge past its last occurrence. Each index enters and leaves the window at most once, so O(n) with a map of last positions, against O(n^2) or worse for checking every substring.

   Follow-up Now allow at most k distinct characters instead of no repeats.

   Still a window: keep a count per character and shrink from the left while the number of distinct characters exceeds k. O(n).

   Learn more Clinic #06 - Longest Substring Without Repeating Characters · Interview Patterns

7. 07Given a list of positive integers and a target, find the length of the shortest contiguous run whose sum is at least the target.

   Sliding window. The tell: contiguous, and because every number is positive, adding an element can only raise the sum and removing one can only lower it.

   Grow the right edge until the sum reaches the target, then shrink from the left while it still does, recording the length each time. Both edges only move forward, so O(n), against O(n^2) for every start and end.

   Follow-up Now the numbers can be negative, and you want to count the runs that sum to exactly k.

   The window breaks: with negatives, growing the window can lower the sum, so there is no rule for which edge to move. Use prefix sums and a hash map of how many times each prefix sum has appeared; at each position add the count of (prefix - k). O(n) time, O(n) space.

   Learn more Arrays & Strings

8. 08Given two strings, find the shortest stretch of the first that contains every character of the second, counting repeats.

   Sliding window with a count of what is still missing. The tell: a contiguous stretch, "shortest", and a condition (contains everything) that once met stays met as the window grows.

   Expand right until nothing is missing, then shrink from the left while it still covers, recording the smallest. Track a single "characters still needed" counter so each step is O(1) instead of re-comparing two count tables. O(|s| + |t|) overall.

   Follow-up Now the order of the characters in the second string must be preserved, as a subsequence.

   The window no longer works, because covering is not just about counts. A 2-D DP over the two strings, or a forward-then-backward scan from each match, is the usual answer. Saying the window breaks, and why, is the point of the question.

   Learn more Interview Patterns

9. 09A string contains only brackets of three kinds. Say whether every bracket is closed by the right kind in the right order.

   Stack. The tell: nesting. The most recently opened bracket is the one that must close next.

   Push each opener; on a closer, the top of the stack must be its partner, so pop and compare. Valid when you finish with an empty stack. O(n) time and O(n) space, and there is no simpler correct approach once there is more than one bracket type.

   Follow-up Now there is only one kind of bracket.

   A counter is enough: +1 for open, -1 for close, fail if it ever goes negative, and it must end at zero. O(1) space. The stack only exists to remember WHICH kind is open.

   Learn more Clinic #07 - Valid Parentheses

10. 10Given a list of daily temperatures, for each day say how many days you must wait for a warmer one.

    Monotonic stack. The tell: for each element, find the next one that is bigger.

    Keep a stack of indices whose temperatures are decreasing. When a warmer day arrives, it is the answer for every colder day on top, so pop them and record the gap. Every index is pushed and popped at most once: O(n), against O(n^2) for scanning forward from each day.

    Follow-up Now find the largest rectangle that fits under a histogram of bar heights.

    Still a monotonic stack, kept increasing. When a shorter bar arrives, each taller bar you pop has found its right boundary, and the new top of the stack is its left boundary; its rectangle is height times that width. O(n).

    Learn more Clinic #08 - Daily Temperatures

11. 11A sorted list was rotated at some unknown point, so it looks like 4, 5, 6, 7, 0, 1, 2. Find a target in O(log n).

    Binary search. The tell: "O(log n)" on something that was sorted. Even rotated, one half of any split is still in order.

    At each midpoint, check which half is sorted by comparing its ends; if the target is inside that sorted range, search there, otherwise search the other half. Each step halves the range: O(log n) against O(n) for a scan.

    Follow-up Now the list can contain duplicates.

    When the left end, middle and right end are all equal, you cannot tell which half is sorted, so you shrink both ends by one. The worst case degrades to O(n), and saying so is the expected answer.

    Learn more Clinic #12 - Search in Rotated Sorted Array · Clinic #11 - Binary Search

12. 12Someone has piles of bananas and h hours. Each hour they eat up to s bananas from one pile. Find the smallest s that lets them finish in time.

    Binary search on the answer. The tell: "find the smallest value that works", and checking any one value is easy and monotonic: if speed s works, every faster speed works too.

    The answer lies between 1 and the biggest pile. Binary search that range, and for each candidate sum ceil(pile / s) over the piles and compare with h. That is O(n log M) for n piles and largest pile M, against O(n M) for trying every speed.

    Follow-up Now split a list into m contiguous parts so the largest part's sum is as small as possible.

    The same pattern. Binary search the maximum allowed sum between max(list) and sum(list); the check greedily cuts a new part whenever the running sum would exceed it and counts parts. O(n log S).

    Learn more Interview Patterns · Sorting & Searching

13. 13Build a store where each key holds values written at increasing timestamps, and a read asks for a key's value as of time t: the latest one written at or before t.

    Binary search over each key's list of timestamps. The tell: timestamps arrive in increasing order, so each key's list is sorted for free, and "latest at or before t" is a boundary search.

    A write appends to the key's list in O(1). A read binary searches for the last timestamp not greater than t, O(log n) per read, against a linear scan back through every version.

    Follow-up Now writes can arrive with timestamps out of order.

    Appending no longer keeps the list sorted. Use a balanced search tree or sorted map per key and ask for the floor of t: O(log n) for both writes and reads.

    Learn more Clinic #11 - Binary Search

14. 14Given the head of a linked list, say whether following the next pointers ever loops back, using constant extra memory.

    Fast and slow pointers (Floyd). The tell: a linked list, a possible cycle, and "constant memory", which rules out a set of visited nodes.

    Move one pointer one step and the other two steps. If there is a cycle, the fast one gains one node per step inside it and must land on the slow one; if not, it reaches the end. O(n) time, O(1) space, against O(n) space for a visited set.

    Follow-up Now return the node where the cycle begins.

    After they meet, move one pointer back to the head and advance both one step at a time. They meet again exactly at the start of the cycle. Still O(n) and O(1).

    Learn more Interview Patterns · Linked Lists, Stacks & Queues

15. 15Design a cache with a fixed capacity where reading or writing a key makes it the most recent, and a write into a full cache throws out the least recently used key. Both operations must be O(1).

    Hash map plus a doubly linked list. The tell: O(1) lookup by key AND O(1) reordering by recency. No single structure does both.

    The map goes from key to list node, so you find any entry in O(1). The list keeps recency order; with prev and next pointers you unlink a node and move it to the front in O(1), and evict from the back in O(1). A plain array or a singly linked list makes the move O(n).

    Follow-up Now evict the least FREQUENTLY used key instead, breaking ties by recency.

    Keep a map from frequency to its own recency list, plus the current minimum frequency. A hit moves the node from list f to list f+1; eviction takes from the back of the minimum-frequency list. Still O(1) per operation.

    Learn more Linked Lists, Stacks & Queues · Hashing

16. 16Standing to the right of a binary tree, list the node you would see on each level, top to bottom.

    Breadth-first search, level by level. The tell: "on each level".

    Run BFS with a queue, processing one level at a time by first reading the queue's length; the last node dequeued on each level is the one visible from the right. O(n) time, O(w) space for the widest level.

    Follow-up Can you do it with DFS instead?

    Yes. Recurse right child first, carrying the depth; the first node you reach at each new depth is the visible one. O(n) time, O(h) space for the height.

    Learn more Clinic #09 - Maximum Depth of Binary Tree · Trees

17. 17Say whether a binary tree is a valid binary search tree.

    DFS carrying a valid range down from the parent. The tell: the rule is about the WHOLE subtree, not just the children, so each node inherits bounds from every ancestor.

    The trap is checking only left < node < right, which accepts a small value deep in a right subtree. Pass (low, high) down: going left tightens high to the node's value, going right tightens low. O(n) time, O(h) space. An in-order traversal that checks the values are strictly increasing is the equivalent answer.

    Follow-up Now find the kth smallest value in a valid BST.

    In-order traversal visits values in sorted order, so stop at the kth visit. O(h + k), not O(n), if you stop early.

    Learn more Trees

18. 18Find the number of edges on the longest path between any two nodes in a binary tree. The path does not have to pass through the root.

    Post-order recursion that returns one thing and updates a global best with another. The tell: the answer at a node needs results from both children first.

    Each call returns its subtree's height; at each node, left height plus right height is the longest path bending there, so update a running maximum. One pass, O(n). Calling a separate height function at every node is O(n^2) on a skewed tree.

    Follow-up Now nodes have values, some negative, and you want the path with the largest sum.

    Same shape. Return the best one-sided gain from each child, clamped at zero because a negative branch is better left off, and update the global best with node + left gain + right gain. O(n).

    Learn more Clinic #10 - Diameter of Binary Tree

19. 19Support adding words to a dictionary and, as someone types, returning every stored word that starts with what they have typed so far.

    Trie. The tell: many strings, and the question is about prefixes.

    Each node is one character and a path from the root spells a prefix. Finding the prefix node costs O(L) for a prefix of length L no matter how many words are stored; everything below it is the answer. A hash set of words would have to test every word for the prefix.

    Follow-up Now return only the three most popular completions.

    Store the top three completions (by count) at each node and update them on insert. A query becomes an O(L) walk and a read, instead of collecting the whole subtree and sorting it.

    Learn more Trees (BST, balancing, heaps, tries)

20. 20Given a grid of letters and a long list of words, return every word that can be spelled by a path of adjacent cells, using each cell at most once per word.

    Trie plus backtracking on the grid. The tell: MANY words searched on the same grid. One word would be plain backtracking; many words share prefixes.

    Put all the words in a trie, then start a DFS from each cell and walk the trie alongside it. A path is abandoned as soon as it is not a prefix of any word, so one grid walk serves every word, instead of one full backtracking search per word. Removing found words from the trie keeps later searches from revisiting them.

    Follow-up Now there is only one word to find.

    Drop the trie. Plain backtracking: DFS from each cell matching the next letter, marking cells visited on the way down and unmarking on the way back.

    Learn more Trees (BST, balancing, heaps, tries)

21. 21Numbers arrive one at a time forever. After each one, report the kth largest seen so far.

    Min-heap of size k. The tell: "kth largest" on a stream you cannot store and sort.

    Keep only the k largest values in a min-heap; the smallest of them, the root, is the kth largest overall. A new number bigger than the root replaces it in O(log k). Re-sorting after every arrival would cost O(n log n) each time.

    Follow-up Now it is a single array you have all at once, asked once.

    Quickselect: partition like quicksort but recurse into one side only, O(n) on average and O(n^2) worst case. A size-k heap, O(n log k), is the safe answer if the worst case matters.

    Learn more Clinic #19 - Kth Largest Element in an Array

22. 22Numbers arrive one at a time. At any moment, report the median of everything seen so far.

    Two heaps: a max-heap for the lower half and a min-heap for the upper half. The tell: you need the middle of a set that keeps growing, and only the middle.

    Keep the heaps balanced to within one element; the median is the top of the bigger heap, or the average of both tops. Adding is O(log n) and reading the median is O(1), against O(n) per insert into a sorted array.

    Follow-up Now report the median of only the last k numbers.

    Removals are now needed, which heaps do badly. Use a sorted multiset (a balanced tree) of the window, O(log k) per step, or keep the two heaps with lazy deletion and rebalance.

    Learn more Trees (BST, balancing, heaps, tries)

23. 23Given a set of distinct positive numbers and a target, list every combination that sums to the target. Each number may be used as many times as you like.

    Backtracking with pruning. The tell: "list every combination". The output itself can be exponential, so no polynomial algorithm exists.

    Recurse with a start index so each combination is built in one order and never repeated; choose a number, recurse with the reduced target, then un-choose. Sorting first lets you stop the loop as soon as a number exceeds what is left, which cuts whole branches.

    Follow-up Now each number may be used once, and the input can contain duplicates.

    Recurse from i + 1 instead of i, and after sorting skip a number equal to the previous one at the same depth. That removes duplicate combinations without a set.

    Learn more Clinic #14 - Combination Sum · Clinic #13 - Subsets

24. 24Place n queens on an n by n chessboard so that no two share a row, column or diagonal, and list every arrangement.

    Backtracking, one row at a time. The tell: place pieces under rules, and list every valid placement.

    Put one queen per row, which removes the row constraint entirely. Keep three sets: used columns, used r - c diagonals and used r + c diagonals, so checking a square is O(1). Pruning a square the moment it is attacked keeps the search far below the n^n raw placements, though it is still exponential.

    Follow-up Now only count the arrangements, for n up to about 15.

    Same search, but track the three sets as bitmasks so a whole row's safe squares come out of one expression. The complexity class is the same; the constant drops a lot.

    Learn more Algorithm Design Patterns

25. 25A grid is made of land and water cells. Count the separate pieces of land, where land connects up, down, left and right.

    Graph traversal: flood fill with DFS or BFS. The tell: a grid where adjacent cells form groups. A grid is a graph whose edges you do not have to store.

    Scan every cell; each time you hit unvisited land, count one and flood-fill everything connected to it, marking it visited. Every cell is visited a constant number of times: O(rows x cols).

    Follow-up Now land is added one cell at a time, and you must report the count after each addition.

    Union-find. Each new land cell starts as its own group, then unions with its land neighbours, decrementing the count on each successful union. Nearly O(1) per addition with path compression and union by rank, instead of a full flood fill each time.

    Learn more Clinic #15 - Number of Islands · Graphs

26. 26In a grid of fresh and rotten fruit, each minute every rotten piece spoils its fresh neighbours. How many minutes until nothing fresh is left, or is it impossible?

    Multi-source BFS. The tell: something spreads from SEVERAL starting points at once, one step per unit of time, and you want the time.

    Put every rotten cell in the queue at time zero and run BFS level by level; each level is one minute. The answer is the number of levels needed, and it is impossible if any fresh cell is never reached. O(rows x cols). Running a separate BFS from each rotten cell would repeat the work once per source.

    Follow-up Now fill each empty room with its distance to the nearest exit, where there are many exits.

    The same multi-source BFS, seeded with every exit. The first time BFS reaches a room is its shortest distance, because every step costs the same.

    Learn more Graphs

27. 27There are n courses, and some must be taken before others. Can every course be finished?

    Topological sort, which is cycle detection on a directed graph. The tell: "must come before".

    Build the prerequisite graph. Kahn's algorithm repeatedly takes courses with no remaining prerequisites; if it takes all n, an order exists, and if some are left, they are stuck in a cycle. O(V + E). A DFS that finds a back edge to a node still on the stack is the equivalent answer.

    Follow-up Now return an order to take them in.

    The order Kahn's algorithm removes courses in is a valid order. Same O(V + E), and an empty result if there is a cycle.

    Learn more Clinic #16 - Course Schedule · Graphs

28. 28A network started as a tree, then one extra link was added, creating exactly one loop. Edges arrive in a list; return the one that closed the loop.

    Union-find. The tell: edges arrive one at a time, and the question is "were these two already connected?"

    Process edges in order; for each one, if both ends already share a root, this edge closes a loop, so return it. Otherwise union them. With path compression and union by rank each operation is nearly O(1), so O(E) overall, against a fresh DFS per edge at O(E^2).

    Follow-up Now just count how many separate groups n nodes form under a list of edges.

    Same structure: start with n groups and subtract one for every union that actually merges two different roots.

    Learn more Graphs

29. 29A signal is sent from one node in a network where each directed link has a travel time. How long until every node has received it?

    Dijkstra's algorithm. The tell: shortest paths from one source, with non-negative weights that differ, so plain BFS no longer counts correctly.

    Use a min-heap keyed by distance; always settle the closest unsettled node and relax its out-edges. The answer is the largest shortest distance, or impossible if a node is unreached. O(E log V) with a binary heap.

    Follow-up Now find the cheapest route that uses at most k stops.

    Dijkstra's greedy choice ignores the stop limit, so run Bellman-Ford for k + 1 rounds, copying the previous round's distances each time so a round extends paths by only one edge. O(k x E).

    Learn more Shortest Paths, Worked · Graphs

30. 30Houses along a street each hold some money. You cannot take from two neighbouring houses. What is the most you can take?

    1-D dynamic programming. The tell: a best score over a sequence, where each choice (take this one or not) only depends on the last one or two choices.

    best[i] = max(best[i-1], best[i-2] + money[i]): either skip house i, or take it and whatever was best two back. Only the last two values are needed, so O(n) time and O(1) space. Trying every subset is O(2^n).

    Follow-up Now the street is a circle, so the first and last houses are neighbours.

    Run the same DP twice, once without the first house and once without the last, and take the better. Still O(n).

    Learn more Clinic #02 - Climbing Stairs · The DP table (lab)

31. 31Given coin values and an amount, find the fewest coins that make up the amount exactly. You have unlimited coins of each value.

    1-D dynamic programming over the amount (unbounded knapsack). The tell: "fewest" plus choices that overlap, and a greedy "take the biggest coin" that fails on some coin sets.

    fewest[a] = 1 + min over coins c of fewest[a - c]. Fill from 0 up to the amount: O(amount x coins). The trap is greedy: with coins 1, 3 and 4 and amount 6, greedy takes 4 + 1 + 1, three coins, but 3 + 3 is two.

    Follow-up Now count the number of different combinations that make the amount.

    Still DP, but put the loop over coins OUTSIDE the loop over amounts. Coins-inside counts 1+2 and 2+1 as different; coins-outside counts each combination once. Same O(amount x coins).

    Learn more Clinic #03 - Coin Change · Dynamic Programming, Worked

32. 32Given a string with no spaces and a dictionary, say whether the string can be split into a sequence of dictionary words.

    1-D dynamic programming over prefixes. The tell: the same suffix gets re-checked by many different ways of splitting the front.

    ok[i] is true when some j < i has ok[j] true and s[j:i] in the dictionary. That is O(n^2) substring checks, or O(n x L) if you only try j within the longest word length L. Plain recursion without memo re-solves the same suffixes and is exponential.

    Follow-up Now return every possible sentence, not just yes or no.

    Backtracking with memoisation on the start index. The output alone can be exponential in size, so no algorithm beats that; memo only stops you recomputing the same suffix.

    Learn more Dynamic Programming, Worked

33. 33Find the minimum number of single-character inserts, deletes and replacements that turn one word into another.

    2-D dynamic programming over both strings. The tell: two sequences, and the answer for a pair of prefixes depends on slightly shorter pairs.

    d[i][j] is the cost for the first i characters of one word and the first j of the other: equal characters cost d[i-1][j-1], otherwise 1 + the min of insert, delete and replace. O(m x n) time, reducible to O(min(m, n)) space with two rows.

    Follow-up Now only inserts and deletes are allowed.

    It becomes m + n - 2 x LCS, where LCS is the longest common subsequence: everything outside the shared subsequence is deleted from one side and inserted from the other. Same O(m x n).

    Learn more Clinic #22 - Longest Common Subsequence · Dynamic Programming, Worked

34. 34A robot starts at the top-left of a grid and can only move right or down. Some cells are blocked. How many routes reach the bottom-right?

    2-D grid dynamic programming. The tell: moves only right or down, so every cell's answer depends on the cell above and the cell to its left.

    ways[r][c] = ways[r-1][c] + ways[r][c-1], or 0 on a blocked cell. O(rows x cols) time, and one row of O(cols) space is enough because you only look one row up. Enumerating paths is exponential.

    Follow-up Now each cell has a cost and you want the cheapest route.

    Same table with min instead of plus: cost[r][c] = grid[r][c] + min(above, left). Still O(rows x cols).

    Learn more Clinic #21 - Unique Paths

35. 35Each position in a list says the furthest you may jump forward from it. Starting at the first position, can you reach the last?

    Greedy: track the furthest reachable index. The tell: you only need to know whether a position is reachable, not how, and reachability only ever grows.

    Walk left to right; if the current index is beyond the furthest reachable, you are stuck; otherwise update furthest with i + jump[i]. One pass, O(n) and O(1). A DP that marks each reachable position from every earlier one is O(n^2).

    Follow-up Now return the fewest jumps needed.

    Still greedy, read as BFS by levels: everything reachable with j jumps is one range; the furthest point reached from inside that range is the end of the next. Count the ranges. O(n).

    Learn more Algorithm Design Patterns

36. 36Find the largest sum of any non-empty contiguous run in a list of integers that may be negative.

    Kadane's algorithm, a greedy running choice. The tell: contiguous run, best sum, and at each element the only question is "extend the run or start over here?"

    best-ending-here = max(x, best-ending-here + x): a negative running sum can only hurt what follows, so drop it. Track the overall best. O(n) and O(1), against O(n^2) for every start and end, or O(n log n) for divide and conquer.

    Follow-up Now find the largest PRODUCT of a contiguous run.

    A negative number flips the smallest product into the largest, so track both the max and the min ending here, and swap them on a negative. Still O(n).

    Learn more Algorithm Design Patterns

37. 37Given a list of time ranges in no particular order, combine every set of overlapping ranges into one.

    Sort by start, then merge in one sweep. The tell: intervals, and an overlap question that is only local once they are in order.

    After sorting by start, a range overlaps the previous merged one exactly when its start is not after that range's end; extend the end, or begin a new range. O(n log n) for the sort and O(n) for the sweep, against O(n^2) comparing every pair.

    Follow-up Now the list is already sorted and non-overlapping, and you insert one new range.

    No sort needed: copy ranges ending before it, merge every range that overlaps it, copy the rest. O(n).

    Learn more Clinic #04 - Meeting Rooms II

38. 38Given the start and end times of many meetings, what is the smallest number of rooms that can host them all?

    Sweep the endpoints, or a min-heap of end times. The tell: intervals, and the answer is the most that overlap at any single moment.

    Sort meetings by start and keep a min-heap of end times of rooms in use; if the earliest end is not after the new start, reuse that room, otherwise add one. The heap's largest size is the answer. O(n log n). Sorting starts and ends separately and sweeping with a counter gives the same.

    Follow-up Now there is one room, and you want to cancel the fewest meetings so the rest fit.

    Greedy by END time: keep the meeting that finishes first, drop any that overlaps it, repeat. Finishing earliest leaves the most room for the rest. O(n log n).

    Learn more Clinic #04 - Meeting Rooms II

39. 39Every number in a list appears exactly twice except one. Find the one, in O(n) time and O(1) extra space.

    XOR everything. The tell: "appears twice" plus "O(1) space" rules out a hash set, and pairs cancelling is exactly what XOR does.

    x ^ x = 0 and x ^ 0 = x, and XOR is order-independent, so XOR-ing the whole list leaves only the unpaired value. O(n) time and O(1) space, against O(n) space for a set of counts.

    Follow-up Now every other number appears three times.

    XOR no longer cancels. Count, for each of the 32 bit positions, how many numbers have that bit set, and take it modulo 3; the leftover bits form the answer. O(32n) = O(n), O(1) space.

    Learn more Bit Manipulation

40. 40Compute x raised to the power n, where n can be as large as two billion.

    Fast exponentiation by squaring. The tell: n too large to multiply n times, and x^n = (x^(n/2))^2 halves the problem every step.

    Square the base and halve the exponent, multiplying into the result whenever the current low bit of n is 1. O(log n) multiplications, against O(n) for the loop, which at two billion is far too slow.

    Follow-up Now n can be negative.

    Compute x^|n| and take the reciprocal. Watch the edge: negating the smallest 32-bit integer overflows, so widen n to 64 bits before flipping its sign.