RaySenseiLEARN WITH RAY · UNDERGRADUATE
Data structures and algorithms
Learn to solve problems with data structures and algorithms in Python. Start from a simple attempt, find the repeated work, then choose a better structure.
One step at a time.
Short lessons. Time to practise.
Learn at your own pace.
Choose a lesson, or search this topic.
Computing / DSA / Undergraduate / Problem solving
140small concepts
16 subtopics · your own pace
16 subtopics · your own pace
Foundations: how to approach an unfamiliar problem
Turn a story into a task, attempt a baseline, locate repeated work and test whether a proposed state is sufficient.
- Separate the goal from the story ▶
A delivery story hides a precise input-output task. Identify inputs, allowed outputs, constraints and tie rules; distinguish finding any valid answer from finding the best one. Ask a clarifying question before picking a technique. - Build an honest brute-force baseline ▶
Try all pairs before trying to optimize pair-sum. Enumerate each pair of distinct indices once and use the baseline as a small-input reference. Explain why a slow correct method is useful and why a guessed shortcut is not yet an improvement. - Find the repeated work ▶
A pair-search repeatedly asks whether a needed partner exists. Separate necessary output work from repeated lookup work; propose what information would make the next decision cheaper before naming a structure. - Keep enough information for the next decision ▶
Two histories may have the same total but leave different future choices. Propose a compact state and challenge it with two histories that look identical under that state yet need different future behavior. This is a design test, not a recipe to remember everything. - Describe operations before choosing storage ▶
A help desk needs operations before it needs a class name. Specify an abstract data type by observable operations and error cases, then compare two representations against its workload. A stack or priority queue is a contract, not a particular layout. - Explain what remains safe after an update ▶
After scanning a prefix, a running maximum should describe exactly that prefix. Trace one update and explain the maintained fact in everyday language; only then call it an invariant. Check the starting state, preservation and the stopping condition using small examples. - Worked problem: Find the first repeated ticket — choose an approach ▶
Scan tickets [A,B,C,B,A] and return the value whose second occurrence is earliest; return no result if all are distinct. Clarify first repeated versus smallest value or earliest first occurrence. Try comparing each new ticket with earlier tickets; discover that remembering previously seen values answers exactly the next question. - Worked problem: Find the first repeated ticket — trace and explain ▶
Scan tickets [A,B,C,B,A] and return the value whose second occurrence is earliest; return no result if all are distinct. Trace the seen set before each ticket. Stop at the second B, index 3 (zero-based), not at A; check [A,A] and an all-distinct input. Explain why adding before testing incorrectly flags the first ticket.
Costs that guide a design decision
Use measured operation counts to choose promising directions and make time-space trade-offs explicit.
- Choose what work to count ▶
Two implementations may look equally short but do different work. Choose input size and a basic operation. Distinguish indexing from slicing and key comparison from whole-string work; state a word-sized-value assumption when using constant-cost arithmetic. - Use growth rates to narrow the options ▶
Doubling input can double, quadruple or barely change a work count. Use tiny counts and doubling/halving first, then relate them to linear, quadratic and logarithmic growth. Distinguish an eventual upper bound O from a matching lower bound Ω and a tight class Θ. - Separate worst-case, expected and amortized claims ▶
A lookup can be usually fast and occasionally expensive. Distinguish a maximum over allowed inputs, an average under a stated probability model, and a total over an operation sequence. Compute a tiny finite average; no probability course is assumed. - Count the work actually executed ▶
A triangular loop does not do n*n iterations exactly. Sum small per-iteration counts before identifying growth; distinguish nested independent scans from a pointer that only advances across the entire run. - Read a recursion tree as a work ledger ▶
Recursive code hides how many subproblems are created. Expand a small recursion tree and count work per level; distinguish one half-size branch, two half-size branches plus linear combining, and two nearly full-size repeated calls. Formal recurrence-solving recipes are deferred. - Account for retained information ▶
A faster algorithm may keep extra tables or pending calls. Separate input, required output and auxiliary storage; count maximum simultaneously retained state, including slices and recursion frames. Time and space are independent comparisons. - Worked problem: Count repeated prefix copies — choose an approach ▶
For n items, compare summing the first i items from scratch for every i=1..n with extending a running prefix total. Both must output all n prefix sums. Count additions on n=4 before naming growth. Repeated sums cost 1+2+3+4 additions; the running total uses four. Include the n-element required output in both versions. - Worked problem: Count repeated prefix copies — trace and explain ▶
For n items, compare summing the first i items from scratch for every i=1..n with extending a running prefix total. Both must output all n prefix sums. For [2,1,3,2], produce [2,3,6,8], then count 10 versus 4 additions. Separate O(n) output storage from O(1) auxiliary running state; a slice-copy baseline also allocates temporary storage.
Arrays: make room without repeating work
Start with contiguous slots, encounter costly insertion and growth, then derive spare capacity and circular storage.
- Why an indexed array is fast ▶
A row of fixed-size slots allows direct access by position. Explain the address-plus-offset model and why indexing is constant-time under it. Contrast a Python list of object references with an imaginary packed array of numeric values. - Why insertion near the front moves work ▶
Insert a new first item while preserving sequence order. Trace the shifts required in a packed array and relate the cost to the number of items after the insertion point. Distinguish known-position access from changing length. - Separate the number of items from available slots ▶
A sequence outgrows its backing array. Track length and capacity independently; when full, allocate a larger array and copy retained entries. Explain why growing by one repeatedly is a costly baseline. - Spread occasional resizing over many appends ▶
Doubling capacity makes some appends expensive but infrequent. Count copies across capacities 1,2,4,8 to develop the geometric-total intuition. Conclude amortized constant append under this model, not worst-case constant append or a claim that Python always doubles. - Reuse freed positions in a queue ▶
Removing a front element should not shift every remaining item. Use a head index and length with modular wraparound in a supplied fixed-capacity array. Derive the next insertion position and distinguish full from empty; resizing can reuse the earlier array policy. - Worked problem: Reuse a bounded request queue — choose an approach ▶
A fixed-capacity queue of four slots receives A,B,C, removes two requests, then receives D,E. New arrivals must preserve FIFO order without shifting every item. Compare shifting the array on dequeue with remembering the head and length. Derive tail=(head+length)%capacity using a four-slot drawing. Choose rejection on overflow; do not silently overwrite live requests. - Worked problem: Reuse a bounded request queue — trace and explain ▶
A fixed-capacity queue of four slots receives A,B,C, removes two requests, then receives D,E. New arrivals must preserve FIFO order without shifting every item. Starting head=0,length=0, trace the operations: final head=2,length=3, physical slots [E,B,C,D], logical order [C,D,E]. B is stale and excluded. Enqueue F to fill the queue, then show G rejected.
Linked structures: which references save work?
Motivate links through edits, repair references carefully and compare them with indexed arrays.
- Change links instead of shifting entries ▶
Frequent insertion after a known item makes array shifts unattractive. In a supplied node-record scaffold, splice a new node after a known predecessor while retaining the old successor. Distinguish constant-time rewiring from the time needed to find that predecessor. - Deletion needs access to the right links ▶
Removing a known value is not the same as already having its predecessor. Unlink a node through its predecessor, handling the head case with a supplied sentinel. Do not promise constant time for searching by value or arbitrary singly linked tail deletion. - Pay for a backward link when it saves a search ▶
A cursor must move and delete in both directions. Use next and prev references and repair both sides when splicing. Explain the additional space and the local consistency rule after tracing the operation. - Keep a tail only if you maintain it ▶
A linked queue should append without scanning to the end. Maintain head and tail references for enqueue/dequeue, including transitions between zero and one item. Use record scaffolds rather than requiring object-oriented syntax. - Choose a sequence layout for its workload ▶
An editor cursor and a scan-heavy numeric list have different needs. Compare arrays and linked structures for indexing, known-position edits, traversal and memory overhead. Reject the slogan that insertion is always faster in a linked list. - Worked problem: Remove the current playlist item — choose an approach ▶
A doubly linked playlist A<->B<->C has a direct reference to the current item B. Remove it and continue at its successor; if there is no successor, continue at its predecessor, or None if empty. Handle first and last items too. Compare searching from the head with using the supplied reference. Identify exactly the predecessor and successor links that must change; head and tail need updates at boundaries. - Worked problem: Remove the current playlist item — trace and explain ▶
A doubly linked playlist A<->B<->C has a direct reference to the current item B. Remove it and continue at its successor; if there is no successor, continue at its predecessor, or None if empty. Handle first and last items too. Reconnect A and C before discarding B; state the new current item C. Then remove the current C: tail and current become A. Remove singleton A: head, tail and current become None. Explain why constant-time deletion assumes the target reference is already available.
Reuse work and discard impossible candidates
Explore interval and search problems from direct scans; make every shortcut depend on an explicit property.
- Precompute what repeated range queries reuse ▶
Summing every requested interval rescans the same values. Store a prefix sum with an initial zero; derive the half-open range total P[r]-P[l] by cancelling the shared prefix. State preprocessing cost and why later updates invalidate affected prefixes. - Use sorted order to discard pairs safely ▶
Trying every pair ignores the information in sorted order. For two-sum on a sorted array with distinct indices, move the left or right endpoint according to the sum. Explain which impossible pairs each move discards; preserve original indices if the caller needs them. - Update a fixed-length window instead of rebuilding it ▶
Neighboring windows share all but two boundary items. For a fixed window size, subtract the outgoing value and add the incoming one; handle invalid sizes through the contract. This sum update remains valid with negative values. - Shrink a window only when the condition permits it ▶
Find the shortest subarray reaching a target sum. For nonnegative values and a positive target, grow the right endpoint and shrink while the target remains met. Develop the monotonicity intuition before the algorithm; a negative-value example shows why the same discard argument fails. - Search for a boundary, not just an equal value ▶
A sorted list can contain repeated keys or no match. Maintain a half-open interval containing the first position with value at least x; equality narrows toward the left. Return n when no position qualifies, and relate the result to insertion position. - Turn boundary searches into duplicate counts ▶
Counting all matches by scanning repeats work in a sorted dataset. Find the first position strictly greater than x and subtract lower_bound(x) to count occurrences. Contrast >= and > at the branch that controls duplicates. - Search possible answers using a feasibility test ▶
A shipping task asks for the smallest daily capacity meeting a deadline. For positive item weights in fixed order, derive a greedy feasibility scan and observe that larger capacity stays feasible. Binary-search the first feasible capacity inside justified bounds; include feasibility-check cost. - Choose what enables the shortcut ▶
A range query, pair search and threshold problem can all look like scans. Compare prefix reuse, sorted elimination, a moving window and monotone answer search by their assumptions. A familiar story word is not evidence that the technique applies. - Worked problem: Find the shortest sufficient positive segment — choose an approach ▶
For positive amounts [2,3,1,2,4,3], find the shortest contiguous segment with sum at least 7, returning a half-open index range. Start with enumerating segments. Explain why positive values allow extending the right boundary and shrinking a sufficient window; state the sum and window boundaries before tracing. If ties occur, return any shortest segment. - Worked problem: Find the shortest sufficient positive segment — trace and explain ▶
For positive amounts [2,3,1,2,4,3], find the shortest contiguous segment with sum at least 7, returning a half-open index range. Trace growing and repeated shrinking until [4,3] at indices [4,6) gives length 2. No single item reaches 7. Test an impossible target and explain why the rule needs reconsideration for negative numbers.
Sorting and selection: how much order is needed?
Start from the caller’s ordering requirement, then compare local insertion, partitioning, selecting one rank and bounded-key counting.
- Decide what ordering must preserve ▶
Sorting records by a key may discard a useful existing order. Specify the comparison key, whether mutation is allowed and whether equal-key records must retain order. Introduce stability through a concrete record example, not through an algorithm name. - Insert into the part already organized ▶
A small nearly sorted hand of cards suggests local insertion. Grow a sorted prefix by shifting only larger keys before inserting the next record. Explain stability from the strict comparison and compare nearly sorted with reverse-ordered input. - Separate around a pivot without sorting everything ▶
To place a pivot, only its relation to each item matters. Trace a supplied partition loop with explicit regions and a chosen pivot convention. Explain each swap by what is known about the regions; duplicates need a stated policy. - Sort the independent pieces after partitioning ▶
Partitioning creates smaller sorting problems around a fixed pivot. Recurse only on the unresolved regions with shrinking bounds. Contrast balanced splits and repeatedly extreme pivots; random pivot choice gives expected, not worst-case, O(n log n) under the stated model. - Follow only the side containing the wanted rank ▶
Finding one median need not sort every item. After partitioning, compare the pivot rank with the target and keep just the relevant region. Explain expected linear work with random pivots and quadratic worst case; use a stated rank convention. - Understand what comparison sorting cannot avoid ▶
Sorting must distinguish many possible orders of distinct keys. Use a small comparison decision tree to motivate the n! possible orders and the worst-case Ω(n log n) comparison lower bound. Restrict the claim to comparison sorting; no long factorial proof is required. - Use a small key universe instead of comparisons ▶
If integer keys lie in a known small range, count by key. Derive frequency counting and reconstruct sorted keys in O(n+U) time and O(U) auxiliary counters. A stable record-sorting variant needs position bookkeeping; it is not achieved by emitting bare keys. - Worked problem: Select a rank without sorting everything — choose an approach ▶
Find the third smallest value (counting duplicates separately) in [7,2,9,4,1,6]. Only the value is required, not a sorted output. Compare full sorting with partitioning around a supplied pivot. With pivot 4, partition into values below, equal to and above it; locate the requested rank before deciding whether another partition is necessary. - Worked problem: Select a rank without sorting everything — trace and explain ▶
Find the third smallest value (counting duplicates separately) in [7,2,9,4,1,6]. Only the value is required, not a sorted output. The below values are 2 and 1, so pivot 4 has rank 3 and is the answer. For [2,2,5], rank 2 is 2. Contrast expected linear randomized selection with its quadratic worst case; do not treat a fortunate pivot as a guarantee.
Hashing: retain answers to repeated lookups
Derive an index from a repeated question, handle collisions and reconsider the choice when order or the universe changes.
- Trade repeated searches for an index ▶
Pair-sum needs fast answers about earlier candidates. Derive a seen-value hash-set scan from brute force; query before inserting to avoid reusing the same index. State expected cost under hashing assumptions and extra memory. - Equal keys must agree about their hash ▶
A bucket location only helps if key equality and hashing agree. Use the rule that equal keys have equal hashes, while unequal keys may collide. Keep a stored key’s equality/hash behavior stable; do not identify an object by its hash alone. - Resolve collisions with local search ▶
Several keys land in one bucket. Implement get/set in a supplied list-of-buckets table: compare keys within the bucket, replace an existing mapping, or append a new entry. Distinguish stored entry count from occupied bucket count. - Resize the index when buckets grow crowded ▶
More insertions can make a previously useful hash table slow. Track load factor entries/buckets and rebuild under a larger bucket count, recomputing each bucket location. Explain why copying buckets unchanged does not perform a rehash. - A missing key may lie beyond a collision ▶
Open addressing keeps entries in the table rather than in bucket lists. Trace linear probing with wraparound; distinguish never-used from deleted slots so a search does not stop too early. Preserve at least one empty slot or a bounded full-cycle rule. - Hashing does not answer every ordered question ▶
Fast equality lookup is different from predecessor or range queries. Compare a hash map, sorted array and direct-address table against updates, ordered queries, universe size and adversarial collisions. Qualify expected costs and key-length work. - Worked problem: Count pairs with a target sum — choose an approach ▶
Count index pairs i<j with a[i]+a[j]=6 in [1,5,1,5,3,3]. Duplicate values represent distinct positions. Use nested pairs as a reference. For each current x, ask how many earlier copies of 6-x exist. A frequency map retains multiplicity; a membership set would lose valid pairs. Query before incrementing the current frequency. - Worked problem: Count pairs with a target sum — trace and explain ▶
Count index pairs i<j with a[i]+a[j]=6 in [1,5,1,5,3,3]. Duplicate values represent distinct positions. Trace contributions 0,1,1,2,0,1 for a total of 5. Check [3,3,3] gives 3 and an empty input gives 0. Explain expected O(n) time under the hash assumptions and O(k) distinct-key storage.
Bitsets and small subset spaces
Turn selection decisions into bits, learn the operations, and check whether the universe and candidate count make the representation useful.
- A selection is a set of decisions ▶
A small collection has many possible selected subsets. Assign one bit position per item, with zero/one denoting exclusion/inclusion. Count 2^n masks and distinguish a compact representation from reducing the number of candidates. - Read bitwise operations on tiny examples ▶
A compact selection is stored as a binary integer. Use nonnegative shifts and AND, OR and XOR on four-bit examples. Bit i denotes item i; write most-significant bit first, so 0101 means items 0 and 2. Distinguish bitwise operators from Boolean and/or. - Operate on selections through their bits ▶
Changing one selection should not rebuild a list of names. Derive test, set, clear and toggle for one selected bit using a shifted one-bit mask. Restrict complements to an explicit finite universe; all examples use most-significant-first notation, rightmost bit zero. - Combine many membership answers at once ▶
Two eligibility filters each describe a set of allowed IDs. Use bitwise intersection, union and difference under a shared finite-universe mapping. Explain why different mappings or unbounded complements invalidate the result. - Enumerate candidates when the item count is small ▶
A compact mask makes exhaustive subset search easy to organize. Visit masks 0 through 2^n-1 and decode selected items to evaluate a supplied feasibility rule. Count decoding work too; pruning or another algorithm is needed when n grows. - A bitset is only small relative to its universe ▶
Representing all possible IDs can cost more than storing the selected ones. Compare U membership bits with a sparse set of k values. A bitset operation spans about U/w machine words; Python large integers also take multiple internal words, so arbitrary-width operations are not universally O(1). - Decide whether you need subsets, counts or order ▶
Selecting items does not automatically make a bitmask the right state. Compare a membership mask with a frequency map and an ordered sequence. A mask loses multiplicity and ordering; use the required output to choose representation and decide whether enumeration is affordable. - Worked problem: Find a shared meeting slot — choose an approach ▶
Slots have IDs 0..5. Availability sets are A={0,2,3,5} and B={1,2,5}; find shared slots and then remove blocked slot 5. Compare scanning slot IDs with representing membership in six bits. Declare bit i means slot i and write most-significant bit first. Derive intersection and a finite-universe clearing mask before computing. - Worked problem: Find a shared meeting slot — trace and explain ▶
Slots have IDs 0..5. Availability sets are A={0,2,3,5} and B={1,2,5}; find shared slots and then remove blocked slot 5. Encode A=101101 and B=100110. Intersection=100100 means {2,5}; clear bit 5 to get 000100, or {2}. Explain why the same encoding is wasteful for a few IDs spread across a billion-slot universe.
Trees and ordered maps
Discover why branching can save comparisons, then encounter skewed shapes and motivate balance without a heavy implementation detour.
- Represent branching without assuming sortedness ▶
A hierarchy branches, while a search tree adds an ordering rule. Represent binary nodes with value, left and right fields using supplied records. Distinguish root, leaf, subtree and height from sorted-key properties; define height as edge count with an empty-tree height of -1. - Choose when to process a node ▶
Printing a directory and evaluating children-first require different visit orders. Trace preorder, inorder and postorder using a small supplied recursive skeleton. Derive each order from whether work happens before, between or after child calls rather than memorizing letter sequences. - Use an ordering rule to exclude a subtree ▶
An ordered map needs search without scanning every key. State the whole-subtree BST rule, with distinct keys or an explicit duplicate policy. Follow comparisons to search and insert; time depends on height, not merely on being called a tree. - Replace a removed key without breaking order ▶
Deleting a node with two children cannot simply drop its subtree. Handle leaf and one-child cases, then replace a two-child key/value by its inorder successor and remove that successor from its old place. Trace retained references using a supplied scaffold. - A search tree can collapse into a list ▶
Sorted insertion creates a long chain in an ordinary BST. Compare a chain with a height-balanced shape using the same keys. Relate search cost to height and motivate an enforced balance condition instead of promising logarithmic behavior for every BST. - Repair shape while keeping key order ▶
A local change in shape need not change inorder order. Trace one left and one right rotation, including the transferred middle subtree. Show that inorder keys are unchanged; rotations are a tool, not by themselves a full balancing algorithm. - Pay for balance when ordered updates matter ▶
A workload mixes inserts with predecessor and range queries. Explain the guarantees supplied by a balanced search-tree library and compare them with a sorted array and hash map. Full AVL/red-black insertion and deletion are deferred; do not pretend a single rotation rule implements them. - Worked problem: Find the next appointment — choose an approach ▶
Appointment times are distinct keys in an ordered map. Find the smallest time at least 13 in a BST with root 10, left 5, right 18, and children 12 and 20 under 18. A full traversal is a baseline. Keep the best qualifying candidate: at a key below the target only the right side can help; at a qualifying key retain it and try left for a smaller one. - Worked problem: Find the next appointment — trace and explain ▶
Appointment times are distinct keys in an ordered map. Find the smallest time at least 13 in a BST with root 10, left 5, right 18, and children 12 and 20 under 18. Visit 10,18,12, then a missing right child; retain answer 18. Target 12 returns 12, and target 21 returns no result. Cost is O(h), becoming O(log n) only under a height guarantee.
Priority queues: maintain only useful order
Encounter the insert-versus-remove trade-off, derive heap order and local repair, then use the structure for top-k decisions.
- Find the next most urgent job ▶
Jobs arrive between removals, so sorting once is no longer enough. Compare an unsorted list with a sorted list for insert and remove-min. Ask what partial ordering would reveal the next job without sorting every pair. - Keep only the order needed at the top ▶
A parent no larger than its children exposes a minimum at the root. Combine this min-heap rule with a complete binary-tree shape; derive zero-based parent and child indices from a level-order drawing. Heap order is not a globally sorted array. - Repair upward after one insertion ▶
Adding a last leaf may violate just its path toward the root. Append at the next shape position and swap upward while smaller than the parent. Explain why the rest of the heap remains safe; separate logarithmic repair from occasional backing-array resizing. - Repair downward after taking the minimum ▶
Removing the root leaves a hole that a last leaf can fill. Move the last item to the root and repeatedly swap with the smaller child when necessary. Handle zero and one-item heaps; arbitrary choice of child can leave a violation. - Build from the bottom when all jobs are known ▶
Repeated insertion is a baseline, but leaves already satisfy heap order. Sift down internal nodes from the last parent toward the root. Count that most nodes are near the leaves to motivate linear heap construction, rather than multiplying every node by full height. - Keep only the candidates that can still matter ▶
The k largest items are wanted from a stream of many values. Maintain a min-heap of at most k candidates and replace its smallest only when a better item arrives. Discover why the weakest retained candidate must be accessible; handle k=0, k>n and ties explicitly. - Choose full order or just the next item ▶
A fixed batch and an interleaved stream justify different costs. Compare sorting once, repeated scanning, heap construction and a size-k heap. Use the requested outputs and update pattern to select the approach rather than using a heap whenever a story mentions priority. - Worked problem: Merge two sorted event feeds — choose an approach ▶
Merge feeds [1,4,8] and [2,3,9] in increasing timestamp order while reading each feed forward only. Generalize the idea to k sorted feeds. Scanning all feed heads each time is a baseline. Only the next unseen item in each sorted feed can be globally next; retain one candidate per nonempty feed in a min-heap. Use feed index to break equal-time ties. - Worked problem: Merge two sorted event feeds — trace and explain ▶
Merge feeds [1,4,8] and [2,3,9] in increasing timestamp order while reading each feed forward only. Generalize the idea to k sorted feeds. Output 1,2,3,4,8,9, replenishing only the feed whose head was removed. Handle an empty feed. Explain O(k + N log(k+1)) time, including scanning empty feeds and heap initialization, and O(k) auxiliary space for N emitted events. This also covers k=1.
Model a graph before choosing a traversal
Translate relationships and actions into a model, choose storage, then contrast layer exploration, depth exploration and richer states.
- Decide what the vertices and edges mean ▶
A map, a dependency list and a puzzle can all describe allowed transitions. Propose vertices, edges and direction from the task; keep the model finite and explicit. Explain what an edge means before choosing a traversal. Graphs represent relationships or states, not only geographic places. - Choose how neighbors are stored ▶
A dense table and a sparse neighbor list answer different operations well. Represent a graph with adjacency lists or a matrix and compare O(V+E) versus O(V^2) storage. For undirected adjacency lists count each edge at both ends; fix simple-graph assumptions for the example. - Explore equally costly moves in layers ▶
A maze asks for the fewest moves, not any route. Use a FIFO queue to expand distance layers and mark vertices when enqueued. Each vertex is enqueued once; explain why first discovery gives minimum edge count when every edge has equal cost. - Keep enough information to reconstruct a route ▶
Knowing the destination distance does not reveal the route. Record a parent on first discovery and walk backward from the destination, then reverse the chain. Distinguish the source, unreachable vertices and alternative equally short routes. - Follow a branch and remember where to return ▶
Reachability and exploration order may matter more than shortest distance. Use recursion or an explicit stack to explore depth first, marking visited vertices to avoid cycles. Explain the role of pending work and why a DFS route is not generally shortest. - Distinguish revisiting from finding a directed cycle ▶
A previously seen vertex may be fully processed or still on the current path. For a directed graph, track unvisited, active and finished states; an edge to an active ancestor signals a cycle. Do not apply that rule unchanged to undirected parent edges. - Schedule only tasks whose prerequisites are ready ▶
A dependency graph may have many valid execution orders. Maintain indegrees and a queue of zero-indegree vertices; removing each ready task releases successors. If vertices remain but none are ready, there is a cycle; an order exists exactly for a finite DAG. - A location may not be the whole state ▶
A route through a locked door depends on whether a key has been collected. Compare location-only visited state with (location,has_key). Merge histories only when they have the same future options; derive transitions and a bound on the expanded state count. - Worked problem: Find a route through a small maze — choose an approach ▶
On a 3x3 four-neighbor grid, block (1,1); start at (0,0), finish at (2,2), and give every legal move cost one. Return one shortest route. Turn open cells into vertices and legal moves into edges. A wandering search may find a route without making it shortest; choose BFS because all edges have equal cost. Check neighbors in right, down, left, up order. Mark visited when enqueuing and retain each first parent. - Worked problem: Find a route through a small maze — trace and explain ▶
On a 3x3 four-neighbor grid, block (1,1); start at (0,0), finish at (2,2), and give every legal move cost one. Return one shortest route. Trace levels 0 through 4 and reconstruct (0,0),(0,1),(0,2),(1,2),(2,2). Other four-move routes are valid. Explain why location alone fails if collecting a key changes legal moves.
Shortest paths: when may a choice be final?
Start with improving route estimates, then discover which graph properties allow layers, greedy finalization or repeated relaxation.
- Improve a route estimate through one more edge ▶
A discovered route may later be beaten by another route. Initialize source distance to zero and other distances to infinity; an edge u->v of weight w proposes dist[u]+w for v. Update both estimate and predecessor only on improvement; this operation alone is not a complete shortest-path algorithm. - Finalize the cheapest unsettled candidate ▶
When can we stop revising a route estimate? Develop Dijkstra from repeated minimum selection, then summarize why finalization is safe. State nonnegative weights and use a small negative-edge counterexample instead of claiming the method always works. - Use a priority queue without trusting stale entries ▶
A better route can leave an older queue entry behind. Implement a supplied lazy heap version: push improved (distance,vertex) pairs, discard popped entries whose distances no longer match, and use a tie counter if vertex objects are not comparable. State the lazy variant may store O(E) entries. - Use dependency order when paths cannot cycle ▶
A weighted DAG supplies an order in which all predecessors are processed first. Relax outgoing edges once per vertex in topological order; negative edge weights are allowed because cycles are absent. Explain O(V+E) work under adjacency-list assumptions. - Allow repeated improvements when weights can be negative ▶
A negative edge breaks greedy finalization but not edge relaxation. Interpret pass k as allowing at least all paths with at most k edges; after V-1 full passes, finite shortest simple paths are covered. Assume no reachable negative cycle for this node; the following node examines what happens when that assumption fails. - Detect when no finite best route exists ▶
Going around a reachable cycle may keep reducing the route cost. After V-1 Bellman-Ford passes, another reachable improvement signals a reachable negative cycle. Trace which destinations can be reached from that cycle and therefore have no finite minimum; distinguish an unreachable cycle. - Choose a shortest-path method from the model ▶
Fewest edges, nonnegative costs and acyclic transitions are different guarantees. Compare BFS, Dijkstra, DAG relaxation and Bellman-Ford using actual weight and cycle properties. Check whether the vertex state captures all constraints before choosing the algorithm. - Worked problem: Choose the cheapest delivery route — choose an approach ▶
A directed network has S->A=4, S->B=1, B->A=2, A->T=1, B->T=7, all nonnegative. Find the minimum-cost S-to-T route. Compare fewest-edge BFS with tentative-cost relaxation. A three-edge route may beat a two-edge one. Select Dijkstra and predict which tentative candidate should be explored next before showing the trace. - Worked problem: Choose the cheapest delivery route — trace and explain ▶
A directed network has S->A=4, S->B=1, B->A=2, A->T=1, B->T=7, all nonnegative. Find the minimum-cost S-to-T route. Finalize S,B,A,T with distances 0,1,3,4; reconstruct S,B,A,T. In a lazy heap, the old A=4 entry is stale after A=3. Contrast BFS choosing a two-edge route of cost 5 or 8 and reconsider the method if negative edges are allowed.
Greedy choices and connecting a network
Challenge plausible local rules, develop one exchange argument, and transfer the reasoning to minimum spanning trees.
- Try a greedy rule, then try to break it ▶
Picking the largest coin first feels natural but can use too many coins. Propose a local rule and search small instances for a failure before committing to it. One successful trace is motivation, not evidence of universal optimality. - Keep the future as free as possible ▶
Select the largest number of non-overlapping fixed intervals. Compare earliest start, shortest duration and earliest finish. Use a small exchange argument after examples to justify earliest finish for unweighted intervals; state that touching endpoints are compatible. - Connecting everyone is not the same as short routes ▶
A network must connect all sites at minimum total edge cost. Distinguish an undirected minimum spanning tree from a source shortest-path tree. A disconnected graph yields a spanning forest; allow equal weights and do not promise a unique optimum. - Justify a locally cheapest connection ▶
A selected component needs an edge to reach the rest of the network. Draw the two sides of a cut respecting the already chosen forest. Motivate why a lightest crossing edge can be included in some optimum by replacing a crossing edge on a cycle; ties need not force every optimum to contain it. - Track which vertices are already connected ▶
Repeatedly testing connectivity by a full graph traversal wastes work during edge selection. Use parent-root representatives for find and union in a supplied scaffold; connect roots to merge components. Representatives identify components, not original graph routes. Start with the simple version before optimizing its tree shape. - Avoid tall component trees when merging ▶
Arbitrary root attachment can create long find paths. Keep component sizes at roots and attach the smaller tree to the larger. Develop the doubling intuition for why a node can gain depth only logarithmically many times; no advanced amortized analysis is assumed. - Reuse a find to shorten future searches ▶
Repeated queries follow the same long parent path. During find, redirect visited nodes to the root in a supplied scaffold. Explain why membership stays unchanged and later finds are cheaper; do not claim worst-case constant time. Detailed inverse-Ackermann analysis is deferred. - Add cheap edges that join different components ▶
Sorted candidate edges can grow a forest without creating cycles. Process edges in nondecreasing weight order and use disjoint sets to reject edges whose endpoints are already connected. Justify accepted edges using a cut; count sorting separately from component operations. - Grow one connected region through its frontier ▶
Instead of sorting every edge first, keep the cheapest edge leaving the current tree. Use a priority queue of crossing candidates, ignore stale edges with both ends already inside, and grow the tree. Restart on an unvisited vertex for a disconnected spanning forest; contrast frontier edges with Dijkstra path distances. - Worked problem: Schedule the most compatible sessions — choose an approach ▶
Choose a maximum-cardinality compatible subset of unweighted half-open sessions [0,6),[1,3),[3,5),[5,7),[6,8). Touching endpoints are allowed. Compare earliest start with earliest finish. Explain with a replacement picture why finishing the first chosen session earlier cannot reduce the room left for later compatible sessions; make this argument after the concrete choice. - Worked problem: Schedule the most compatible sessions — trace and explain ▶
Choose a maximum-cardinality compatible subset of unweighted half-open sessions [0,6),[1,3),[3,5),[5,7),[6,8). Touching endpoints are allowed. Earliest finish picks [1,3),[3,5),[5,7), for three sessions. Earliest start gets [0,6),[6,8), only two. Explain why three is optimal here and why adding unequal rewards changes the objective.
Explore choices without losing control of state
Build small choice trees, manage undo correctly and justify pruning before claiming speedups.
- Turn a sequence of choices into a search tree ▶
A complete solution is built through several small decisions. Define a partial candidate, legal next choices and a complete-candidate test. Draw the tiny choice tree before writing recursive code; distinguish exploring all leaves from finding one acceptable leaf. - Restore shared state before exploring a sibling ▶
One recursive branch must not leave its choices in the next branch. Use choose, recurse, unchoose on a mutable candidate, or copy deliberately and account for its cost. Snapshot completed outputs so later mutation does not change previously emitted answers. - Used positions constrain the next choice ▶
A permutation needs each selected position exactly once. Track used positions while extending a partial order, then undo the mark. Distinguish permutations from subsets and explain the factorial output count for distinct items. - Discard a branch only when completion is impossible ▶
A search becomes faster if hopeless partial candidates are recognized early. For nonnegative subset weights, prune when a partial sum exceeds the target. Explain why the rule is unsound if later negative weights are allowed; pruning cannot discard merely inconvenient branches. - Make constraints guide the next choice ▶
Place one queen per row without attacking earlier queens. Represent used columns and two diagonal identifiers, reject conflicts before recursing and restore state after return. Introduce r-c and r+c as labels through a board drawing; full solver optimization is deferred. - Account for output size and worst-case branching ▶
Pruning a few examples does not guarantee polynomial time. Bound a simple choice tree and count required outputs separately from overhead. Choose exhaustive search when candidate count is genuinely small, or seek reusable subproblems when many branches ask the same question. - Worked problem: Find every exact packing — choose an approach ▶
From single-use positive weights [2,3,5], enumerate every subset summing to 5. Return each subset once. Build include/exclude decisions by item index. Keep the chosen items and current sum; prune sums above 5 only because all remaining weights are positive. Snapshot a completed selection and undo changes before exploring its sibling. - Worked problem: Find every exact packing — trace and explain ▶
From single-use positive weights [2,3,5], enumerate every subset summing to 5. Return each subset once. Obtain exactly [2,3] and [5]. Trace the branch [2,5] being pruned and restoring state before another branch. Explain why remaining negative weights would invalidate this pruning rule.
Dynamic programming: reuse answers to the same remaining problem
Begin with a correct choice tree, identify repeated states, then choose a recurrence, evaluation order and representation.
- Notice when different branches ask the same question ▶
Coin-change recursion repeatedly solves the same remaining amount. Draw a tiny brute-force call tree for minimum coins with unlimited positive integer denominations. Identify repeated remaining amounts and distinguish overlapping subproblems from independent divide-and-conquer pieces. - Keep exactly what changes the remaining choices ▶
Remaining amount alone works for unlimited coins but can fail for single-use items. Compare histories with the same proposed state; add an item index when the unused suffix matters. State meanings in a sentence before writing any table. - Express a solution through smaller state answers ▶
A minimum-coins answer can be obtained by trying the last chosen coin. Derive dp[0]=0 and dp[s]=1+min dp[s-c] over positive coins c<=s, with infinity for unreachable states. Explain why positive coin values ensure smaller dependencies. - Remember an answer after computing it once ▶
A correct recursive baseline recomputes equal states. Cache results by the complete state, including unreachable results, and count distinct states times transition work. Memoization does not repair an insufficient state or a cyclic recurrence. - Evaluate states after their dependencies ▶
A table can replace recursive scheduling when dependency order is known. For increasing-amount coin DP, fill smaller amounts first; view the recurrence as a DAG of dependencies. Distinguish the state definition from the choice of memoization versus tabulation. - Retain one choice when the actual solution is required ▶
The optimal value does not reveal which choices attained it. Record a predecessor choice for each improved state and trace back from the target, handling unreachable states and ties with a stated policy. Do not recompute all candidate solutions to recover one. - An item index prevents accidental reuse ▶
Choose single-use items of given weights and values under a capacity. Derive include/exclude choices for state (first i items, capacity w), with an empty-prefix base case. Distinguish 0/1 knapsack from unlimited coin change; describe O(nW) as capacity-dependent, not polynomial in the number of capacity bits. - Overwrite a table only after checking who still needs it ▶
A two-row knapsack table appears to contain old data that can be reused. Reduce the 0/1 value table to one row by processing capacities downward. An upward loop would reuse the current item; discuss what is lost if reconstruction information is discarded. - Represent reachable sums as a set of bits ▶
For yes/no subset-sum, many Boolean states can be updated together. Let bit s mark a reachable sum and update reachable | (reachable << w) from the old bitset for one nonnegative single-use weight. Explain the connection to DP, the sum-range storage cost and why this does not directly compute counts or maximum values. - Worked problem: Find a minimum-coin payment — choose an approach ▶
With unlimited coins 1,3,4, pay amount 6 using the fewest coins; return one optimal selection. Try largest coin first: 4+1+1 uses three. Compare repeated remaining-amount subproblems and derive a table indexed by remaining amount, with zero coins for amount zero and infinity for unreachable states. - Worked problem: Find a minimum-coin payment — trace and explain ▶
With unlimited coins 1,3,4, pay amount 6 using the fewest coins; return one optimal selection. Build values [0,1,2,1,1,2,2] for amounts 0..6. Record choices and reconstruct 3+3. Explain O(amount*number_of_denominations) work and why single-use coins need a different state or transition rule.
Approach labs: recognize structure in unfamiliar problems
Practice proposing, rejecting and adapting approaches across different stories; these are bounded decisions, not demands to invent an algorithm unaided.
- Reconsider the structure when the workload changes ▶
A fast static solution can become slow once updates arrive. Compare prefix sums, scanning and recomputation for a stated mix of queries and updates. Identify when a more advanced range structure is worth studying without pretending it has already been taught. - Try two models before choosing an algorithm ▶
A word-to-document search can be seen as scanning text or combining memberships. Propose an inverted index and a direct scanning baseline, then compare preprocessing, repeated-query cost and update burden. Use the required operation to choose sparse postings or dense bitsets. - Compare local choice, search and reusable states ▶
Selecting tasks can mean maximizing count, maximizing value or respecting dependencies. Use small counterexamples to distinguish greedy interval scheduling from weighted choices needing a different approach. State candidate representations and an experiment that could reject each before selecting a strategy. - Combine structures to support two kinds of access ▶
A recent-item cache needs both key lookup and recency updates. Derive a map from keys to linked nodes plus a doubly linked recency list. Explain synchronized updates and eviction in a small fixed-capacity trace; expected constant-time operations rely on map assumptions. - Defend a choice and revise it when evidence changes ▶
A fresh problem does not arrive labeled with its algorithm. Produce two plausible approaches, a correct tiny baseline, explicit input assumptions, a small distinguishing test and time-space estimates. Use a plain-language correctness summary before optional notation; revise the model when a counterexample appears. - Worked problem: Answer connectivity queries as roads arrive — choose an approach ▶
Begin with isolated towns A,B,C,D. Add road A-B, ask whether A reaches C, add B-C, ask again, then remove B-C and ask once more. Compare rebuilding reachability with keeping connected components using disjoint sets. Treat find/union as a candidate for the additions-only prefix, then notice that the specified deletion rules it out for the full workload. Choose recomputing BFS/DFS for this tiny changing graph; distinguish answering whether a route exists from returning the actual route. - Worked problem: Answer connectivity queries as roads arrive — trace and explain ▶
Begin with isolated towns A,B,C,D. Add road A-B, ask whether A reaches C, add B-C, ask again, then remove B-C and ask once more. Answers are false,true,false. Show that plain union-find still reports A and C together after deletion because it cannot split components. For this tiny changing graph choose recomputing BFS/DFS; advanced dynamic connectivity is deferred.