Honors Class

Problems

25.1

The greatest common divisor (GCD) of positive integers $x$ and $y$ is the largest integer $d$ such that $d$ divides both $x$ and $y$ .

Design an efficient algorithm for computing $g cd (x, y)$ without using multiplication, division, or modulus.

Hint: Use case analysis: both even, both odd, or one even and one odd.

25.2

Let $A$ be an array of length $n$ . Design an algorithm to find the smallest positive integer that is not present in $A$ . You do not need to preserve the contents of $A$ .

For example, if $A = ⟨ 3, 5, 4, - 1, 5, 1, - 1 ⟩$ , the smallest missing positive integer is $2$ .

Hint: First find an upper bound for the answer.

25.3

Design an algorithm that computes the maximum profit that can be made by buying and selling a stock at most $k$ times.

Hint: Generalize the dynamic programming structure for one transaction and two transactions.

25.4

Suppose you are given an array $A$ of integers, and are asked to find the largest product that can be made by multiplying all but one of the entries in $A$ . You may not use an entry more than once.

For example, if $A = ⟨ 3, 2, 5, 4 ⟩$ , the result is $60$ ; if $A = ⟨ 3, 2, - 1, 4 ⟩$ , the result is $24$ ; and if $A = ⟨ 3, 2, - 1, 4, - 1, 6 ⟩$ , the result is $72$ .

Hint: Think in terms of prefix and suffix products, or separate the cases by the counts of negative and zero entries.

25.5

Compute the beginning and ending indices of a longest contiguous increasing subarray of an array.

Hint: Once you know where one increasing run ends, some later starts can be skipped.

25.6

Let $A$ be an array of $n$ elements. Design an algorithm for rotating $A$ to the right by $i$ positions. Do not use library functions implementing rotation.

Hint: Relate the number of cycles to $g cd (n, i)$ .

25.7

You are given a 2D array of $1$ s and $0$ s, where the $0$ s encode rook positions. Compute the squares attacked by the rooks, i.e., set every entry in a rook’s row or column to $0$ .

Hint: Reuse part of the board itself to store markers.

25.8

After justification, each line must begin with a word, and adjacent words on the same line must be separated by at least one blank. If a line contains more than one word, it should not end in a blank. The runs of blanks within a line should be as close to equal in length as possible, with the longer runs, if any, appearing earlier in the line. The final line should be left-justified.

Write a program which takes as input an array $A$ of strings and a positive integer $L$ , and computes the fully justified text specified by $A$ .

Hint: Solve the problem line by line, then distribute the extra blanks.

25.9

Given a singly linked list $L$ , zip it by interleaving the first half with the reversed second half. For example,

⟨ 0, 1, 2, 3, 4, 5 ⟩ \mapsto ⟨ 0, 5, 1, 4, 2, 3 ⟩ .

Implement this transformation.

Hint: It is easy to traverse a list in reverse order after reversing a suffix.

25.10

A postings list is a linked list in which each node has a next pointer and an additional pointer, often called jump, that may point to any node in the list or to null.

Copy a postings list. You may modify the original list during the copy, but you must restore it before returning.

Hint: Copy the jump structure before detaching the copied nodes.

25.11

Problem 9.3 defines matched strings of parentheses, brackets, and braces. Here we restrict attention to strings made only of ( and ).

Write a program that takes as input a string and returns the size of a maximum-length substring in which the parentheses are matched.

Hint: Start with a brute-force algorithm, then reason about how failures let you skip work.

25.12

Network traffic analysis sometimes requires studying traffic volume over time. You are given timestamped traffic values and a fixed window size $w$ .

For each timestamp, compute the maximum traffic over the interval ending at that timestamp and extending back by at most $w$ .

Hint: Think about what queue operations you need if the window changes only at the ends.

25.13

Write a program that takes as input a binary tree and performs a postorder traversal of the tree. Do not use recursion. Nodes do not contain parent references.

Hint: Study the call stack for the recursive version.

25.14

You manage a team of developers. You want to give concert tickets as bonuses. The developers sit in a row. Each developer has a productivity score, and each developer must receive at least one ticket. If a developer is more productive than a neighbor, then that developer must receive more tickets than that neighbor.

Compute the minimum number of tickets needed to satisfy these constraints.

Hint: Consider iteratively improving an assignment that may not yet satisfy the constraints.

25.15

Binary search is usually applied to an array of known length. Sometimes the array is “virtual”, i.e., the length is not known in advance, and accessing elements beyond the end raises an exception.

Design an algorithm that searches a sorted array of unknown length for a key.

Hint: Can divide-and-conquer be used to find the end of the array?

25.16

You are given two sorted arrays and a positive integer $k$ . Design an algorithm for computing the $k$ th smallest element in the sorted union of the two arrays. Entries may be duplicated within an array and across the two arrays.

Hint: The first $k$ elements of the first array together with the first $k$ elements of the second array are initial candidates. Repeatedly eliminate a constant fraction.

25.17

An input sequence is presented one element at a time. Design an algorithm for finding the $k$ th largest element when $n$ is large and $k$ is small.

Hint: Track the $k$ largest elements, but do not necessarily update the collection after every single new element.

25.18

Given an integer array of length $n$ , where each element except one appears twice, the remaining element can be found with XOR.

Now solve the harder version in which each entry but one appears three times. Find the element that appears only once.

Hint: Count the number of $1$ bits at each bit position.

25.19

You are given a set of points in the plane. Each point has integer coordinates.

Design an algorithm for computing a line that contains the maximum number of points in the set.

Hint: A line can be uniquely represented by two numbers.

25.20

Let a query string be given together with a nonempty set of strings $D$ . Return the shortest prefix of the query string that is not a prefix of any string in $D$ . Return the empty string if every prefix of the query string is a prefix of some string in $D$ .

Hint: How would you represent a set of strings as a rooted tree?

25.21

This problem is a continuation of the most-visited-pages-in-a-window API. Each log entry includes a visit time and a page. Only pages whose visit times are no older than a fixed duration $W$ from the most recently read page are considered.

Compute the $k$ most visited pages in the current window. You may assume visit times increase as you process the file.

Hint: Use a federation of data structures.

Variant: Solve the same problem when the logfile can contain multiple visits to a page at the same time, and entries can be out of order with respect to visit time.

25.22

Lists and BSTs are both linked data structures. Consider the problem of converting a sorted doubly linked list into a height-balanced BST.

Design an algorithm that takes as input a sorted doubly linked list and returns a balanced BST on the same keys.

Hint: Build the tree in the same order that an inorder traversal would visit it.

25.23

Take a BST and rewrite its node-reference fields so that it becomes a sorted doubly linked list in inorder order. Do not allocate new nodes. The original BST does not need to be preserved.

Hint: The tricky part is attaching the root to its converted subtrees.

25.24

Given two BSTs, create a height-balanced BST containing the union of their keys. You may update child pointers, but not keys, and should use only a small amount of additional allocation.

Hint: Problems 25.22 and 25.23 are relevant.

25.25

You are given a set of horizontal line segments. Each segment consists of a closed interval on the $X$ -axis, a color, and a height. When viewed from above, the color at point $x$ on the $X$ -axis is the color of the highest segment that includes $x$ .

Write a program that outputs the view from above. You may assume no two overlapping segments have the same height.

Hint: First organize the segment endpoints.

25.26

Implement regular expression matching for a syntax with alphanumeric characters, ., *, ^, and $.

Write a program that takes a regular expression and a string, and checks if the regular expression matches the string.

Hint: Regular expressions are defined recursively.

Variant: Solve the same problem for regular expressions without the ^ and $ operators.

25.27

Consider an expression of the form $⟨ 3 \circ 1 \circ 4 \circ 1 \circ 5 ⟩$ , where each $\circ$ is an operator. In the version here, you may place either multiplication signs or plus signs between adjacent digits, or leave two adjacent digits concatenated.

Write a program that takes an array of digits and a target value, and returns true if it is possible to synthesize an expression that evaluates to the target.

Hint: Build the assignment incrementally.

25.28

Let $A$ be an array of integers. Call the pair of indices $(i, j)$ inverted if $i < j$ and $A [i] > A [j]$ .

Design an efficient algorithm that takes an array of integers and returns the number of inverted pairs.

Hint: Let $A$ and $B$ be arrays. How would you count the number of inversions where one element is from $A$ and the other from $B$ in the array consisting of elements from $A$ and $B$ ?

25.29

A number of buildings are visible from a point. Each building is a rectangle whose bottom lies on a fixed horizontal line. A building is specified by its left and right coordinates and its height. One building may partially obstruct another.

The skyline is the list of coordinates and corresponding heights of what is visible. Design an efficient algorithm for computing the skyline.

Hint: Think of an efficient way of merging skylines.

25.30

You have measuring jugs whose marks are worn out, making it impossible to measure exact volumes. Instead, each use of a jug produces some volume in an interval $[l_{i}, u_{i}]$ . Given several such jugs and a target interval $[L, H]$ , determine whether it is possible to measure a quantity guaranteed to lie within $[L, H]$ .

Hint: Solve the $n$ -jug case recursively.

Variant: Suppose jug $i$ can be used to measure any quantity in $[l_{i}, u_{i}]$ exactly. Determine if it is possible to measure a quantity of milk between $L$ and $U$ .

25.31

Finding the maximum subarray sum in a linear array can be done in linear time. However, if the array is circular, the standard algorithm may yield a suboptimal answer.

Given a circular array $A$ , compute its maximum subarray sum in $O (n)$ time. Can you devise an algorithm that takes $O (n)$ time and $O (1)$ space?

Hint: The maximum subarray may or may not wrap around.

25.32

You need to test the design of a protective case. The case can protect an enclosed device from a fall from up to some critical number of floors. All cases are identical, a surviving case can be reused, and a broken case must be discarded.

Given $c$ cases and a maximum of $d$ allowable drops, determine the maximum number of floors that can be tested in the worst case.

Hint: Write a recurrence relation.

Variant: Solve the same problem with $O (c)$ space.

Variant: How would you compute the minimum number of drops needed to find the breaking point from 1 to $F$ floors using $c$ cases?

Variant: Men numbered from 1 to $n$ are arranged in a circle in clockwise order. Every $k$ th man is removed until only one remains. What is the number of the last man?

25.33

The following problem has applications to image processing.

Let $A$ be an $n \times m$ Boolean 2D array. Design efficient algorithms for the following two problems:

Find the maximum-area rectangular subarray containing only 1s.
Find the maximum-area square subarray containing only 1s.

Hint: If you already know the largest all-1 rectangle or square below and to the right of a cell, how can you reuse that information?

25.34

One way to compress text is by building a codebook which maps each character to a bit string, referred to as its code word. Concatenating the bit strings yields the encoded text.

Implement Huffman coding: given symbols and their frequencies, produce a prefix-free code of minimum weighted average length.

Hint: Think about what the rarest symbols must look like in an optimal tree.

25.35

The goal of this problem is to compute the capacity of a one-dimensional container. A one-dimensional container is specified by an array of $n$ nonnegative integers, where each entry is the height of a unit-width rectangle.

Design an algorithm for computing how much water can be trapped.

Hint: Draw pictures, and focus on the extremes.

Variant: Solve the water-filling problem with an algorithm that accesses the array in order and can read each element only once, using minimum additional space.

25.36

An abs-sorted array is an array of numbers in which $∣ A [i] ∣ \leq ∣ A [j] ∣$ whenever $i < j$ .

Design an algorithm that takes an abs-sorted array $A$ and a number $K$ , and returns a pair of indices of elements in $A$ that sum to $K$ . Output $(- 1, - 1)$ if no such pair exists.

Hint: This problem is easy to solve with $O (n)$ additional space. To solve it with $O (1)$ additional space, first assume all elements are positive.

Variant: Design an algorithm that takes as input an array of integers $A$ and an integer $K$ , and returns a pair of indices $i$ and $j$ such that $A [j] - A [i] = K$ , if such a pair exists.

25.37

This problem generalizes the majority-element problem. You are reading a sequence of strings separated by whitespace. You are allowed to read the sequence twice.

Devise an algorithm that uses $O (k)$ memory to identify the words that occur more than $\frac{n}{k}$ times, where $n$ is the length of the sequence.

Hint: Maintain a list of $k$ candidates.

25.38

Here we consider finding the longest subarray subject to a constraint on the subarray sum.

Design an algorithm that takes as input an array $A$ of $n$ numbers and a key $k$ , and returns the length of a longest subarray of $A$ for which the subarray sum is less than or equal to $k$ .

Hint: When can you be sure that an index $i$ cannot be the starting point of a qualifying subarray without looking past it?

Variant: Design an algorithm for finding the longest subarray of a given array such that the average of the subarray elements is at most $k$ .

25.39

The California Department of Transportation is considering adding a new section of highway to the California Highway System. Each highway section connects two cities, and each proposal specifies a pair of cities together with the length of the new section.

Write a program which takes the existing highway network and a set of proposals, and returns the proposed highway section which leads to the greatest improvement in the total driving distance, defined as the sum of the shortest-path distances between all pairs of cities. The original network is connected and all roads are bidirectional.

Hint: Suppose we add a new section from $b_{s}$ to $b_{f}$ . If the shortest path from $u$ to $v$ passes through this section, what must be true of the path from $u$ to $b_{s}$ ?

25.40

You are in a barter economy with $n$ commodities and a matrix of exchange rates. Transaction costs are zero, exchange rates do not fluctuate, and fractional quantities can be traded.

Design an efficient algorithm to determine whether there exists an arbitrage, i.e., a cycle of trades whose product of exchange rates exceeds 1.

Hint: Recast the multiplicative condition additively.

Answers

25.1

Use Stein’s binary GCD algorithm. Recurse on parity: if both numbers are even, factor out 2; if one is even, drop the factor of 2 from that one; if both are odd, replace the larger by the difference. This avoids division and modulus and runs in $O (lo g x + lo g y)$ time.

25.2

Exploit the fact that if all integers $1$ through $n$ are present, the answer is $n + 1$ . Rearrange the array in place so that value $v$ is moved to index $v - 1$ whenever possible, then scan for the first index $i$ with $A [i] \neq = i + 1$ . This gives $O (n)$ time and $O (1)$ extra space.

25.3

Dynamic programming over day and transaction count works. Track the best states after each buy and sell, or equivalently maintain DP values for the best profit after the $j$ th buy and after the $j$ th sell. Updating these in day order yields $O (kn)$ time and $O (k)$ space.

25.4

Either precompute prefix and suffix products and test skipping each index, or reason directly from the counts of negative and zero entries. The best product is determined by which sign you want and which element it is optimal to exclude. This can be done in linear time.

25.5

Scan once while tracking the current increasing run and the best run seen so far. When a run breaks, start a new one. A further optimization skips some start positions by noticing when a long enough run is impossible, but the core algorithm is still linear.

25.6

View the rotation as a permutation of indices. Apply that permutation cycle by cycle; the number of cycles is $g cd (n, i)$ . An equivalent in-place alternative is the standard three-reversal trick. Both solutions use $O (1)$ extra space.

25.7

Use the first row and first column of the matrix as marker storage. First record whether they themselves originally contain a rook, then mark rows and columns that must be zeroed. A final pass applies the marks. This keeps the space usage at $O (1)$ .

25.8

Pack each line greedily with as many words as fit. Once the line’s word range is fixed, distribute the extra blanks as evenly as possible, giving earlier gaps the longer runs when needed. The final line is handled separately by left-justifying it.

25.9

Find the midpoint of the list, split it, reverse the second half, then interleave nodes from the first half and the reversed second half. This transforms the list in place in $O (n)$ time.

25.10

Interleave each copied node immediately after its original node. Then the copied jump pointer for node $u$ can be set to u.jump->next. After all jump pointers are filled in, detach the copied nodes and restore the original list. This uses $O (1)$ extra space beyond the new nodes.

25.11

Scan the string while maintaining a stack of unmatched left-parenthesis indices and the location of the most recent unmatched right parenthesis. Whenever a match is formed, the current valid suffix length is determined by the stack top or the last unmatched right parenthesis. This yields an $O (n)$ solution.

25.12

Use a queue that supports max in amortized $O (1)$ time, i.e., a monotone deque. Enqueue new traffic samples in timestamp order, evict samples that leave the window, and read off the current maximum after each update. Total time is linear in the number of samples.

25.13

Simulate the recursive traversal with an explicit stack and a prev pointer telling whether you arrived at the current node from its parent, its left child, or its right child. That is enough state to know whether to go left, go right, or visit the node. The traversal is $O (n)$ time and $O (h)$ space.

25.14

Process developers in increasing order of productivity. When a developer is processed, every less-productive neighbor already has its final ticket count, so this developer’s minimum valid count is one more than the maximum such neighbor, or 1 if there is none. A min-heap or sorting by productivity gives the needed order.

25.15

First do exponential search on indices $1, 2, 4, 8, \dots$ until either the key is bracketed or an out-of-bounds exception occurs. Then binary-search within the surviving interval, treating out-of-bounds as “too far right”. The total running time is $O (lo g n)$ .

25.16

Binary-search the number $x$ of elements contributed by the first array to the first $k$ elements of the merged order. If $A [x]$ is too small or too large relative to $B [k - x - 1]$ , adjust the search interval. Once the partition is valid, the answer is the larger of the two left-side boundary elements.

25.17

Maintain only a small candidate set. Keep collecting values until you have about $2 k - 1$ of them, then use selection to discard everything except the $k$ largest and continue. After the stream ends, the root of the remaining size- $k$ min-structure is the answer. This keeps the space at $O (k)$ .

25.18

Count, for each bit position, how many array entries have that bit set. Since all repeated elements contribute multiples of 3, taking each count modulo 3 leaves exactly the bits of the unique value. Reassemble those bits to recover the answer in $O (n)$ time.

25.19

Enumerate pairs of points, derive a canonical representation of the line through each pair, and hash by that representation. The line with the largest associated point set is the answer. Canonicalization matters so that equal slopes and intercepts hash identically.

25.20

Build a trie for the dictionary strings. Then walk the query string character by character. The first time the needed outgoing edge is missing, the prefix up to that character is the shortest prefix not in the dictionary’s prefix set. If the path never breaks, return the empty string.

25.21

Use a queue to evict visits that are more than $W$ time units older than the most recent visit. Alongside it, maintain counts per page and an ordered structure keyed by counts so the top $k$ pages can be reported quickly. This is a small federation of queue, hash table, and balanced-tree logic.

25.22

Build the BST in inorder sequence from the list. Recursively construct the left subtree on the first $⌊ n /2 ⌋$ nodes, use the next list node as the root, then build the right subtree from the remaining nodes. Because the list head advances exactly once per node, the total time is $O (n)$ .

25.23

Convert each subtree recursively into a (head, tail) doubly linked list, then splice left list + root + right list in constant time. Since an inorder traversal of a BST is already sorted, the resulting list is sorted as well. The algorithm is $O (n)$ time and $O (h)$ stack space.

25.24

Convert both BSTs to sorted doubly linked lists, merge the two sorted lists, then convert the merged sorted list back into a balanced BST using the previous problem’s ideas. This yields linear time overall, with extra space dominated by recursion depth.

25.25

Sort all segment endpoints and sweep from left to right. Maintain the active segments in a structure keyed by height. Whenever the tallest active segment changes, emit or extend the visible run for the previous top segment. This is the standard line-sweep solution in $O (n lo g n)$ time.

25.26

Match recursively on the syntax of the regular expression. The core cases are empty regex, end-anchor $, a leading atom followed by *, and a single ordinary or . character. If the regex is unanchored, try matching it against each suffix of the string. This directly mirrors the grammar.

25.27

Build the expression left to right by deciding at each gap whether to concatenate, multiply, or add. Evaluate multiplication before addition, and prune branches that can no longer reach the target, for example when even the largest possible remaining contribution is too small. This is a backtracking search with useful pruning.

25.28

Count inversions with merge sort. Recursively count inversions in the left and right halves, then count cross inversions during the merge: whenever a right-half element is taken before a left-half element, it forms inversions with all remaining left-half elements. This gives $O (n lo g n)$ time.

25.29

Compute skylines recursively: solve the problem for the left half of the buildings and the right half, then merge the two skylines in linear time by advancing through their breakpoints. A line-sweep over endpoints also works, but the divide-and-conquer formulation is the canonical textbook solution.

25.30

Recurse on the remaining target interval. If a jug’s output interval lies entirely inside the desired interval, it can be the final step; otherwise try ending with that jug and solve the residual interval. Memoize impossible intervals so the search does not repeat work. The state space is interval-based.

25.31

Take the maximum of two cases: the best nonwrapping subarray and the best wrapping subarray. The nonwrapping case is ordinary Kadane. The wrapping case can be computed by combining the best prefix ending at or before each index with the best suffix starting after it, or equivalently by subtracting a minimum subarray.

25.32

Let $F (c, d)$ be the maximum number of floors testable with $c$ cases and $d$ drops. If the next drop breaks, you can explore $F (c - 1, d - 1)$ floors below; if it survives, you can explore $F (c, d - 1)$ floors above. Hence

F (c, d) = F (c - 1, d - 1) + 1 + F (c, d - 1) .

Dynamic programming over this recurrence solves the problem.

25.33

For each cell, compute how many consecutive 1s extend downward and rightward from it. That local information lets you test candidate rectangles and squares having that cell as a corner. The rectangle version grows heights while tracking the limiting width; the square version uses the same DP data with a simpler side-length check.

25.34

Huffman coding repeatedly combines the two least-frequent symbols or partial trees into a new tree whose weight is their sum. A min-heap supports these repeated extractions efficiently. The code for each character is the left/right bit sequence on the path from the root to its leaf.

25.35

Find an index of maximum height and sweep outward from it. To the left, keep the tallest wall seen so far and add the gap between that wall and the current height; do the symmetric pass on the right. Since water level rises monotonically toward the global maximum from either side, this computes the trapped volume in linear time.

25.36

Adapt the two-pointer idea to an abs-sorted array by separating the possible sign patterns: both positive, both negative, or one of each. Each case admits a monotone pointer movement rule, and together they yield an overall $O (n)$ -time, $O (1)$ -space algorithm.

25.37

Use the Misra-Gries heavy-hitters generalization of Boyer-Moore. Maintain at most $k$ candidate words with counters; when a new distinct word arrives and all counters are occupied, decrement every counter and delete zeros. After one pass, the true heavy hitters are among the survivors, and a second pass verifies them.

25.38

Build prefix sums together with a suffix array of minimum future prefix sums. Then use two pointers: for a candidate start index $a$ and end index $b$ , determine the smallest achievable subarray sum starting at $a$ and reaching at least $b$ . If it is $\leq k$ , extend $b$ ; otherwise advance $a$ . This yields a linear-time scan after the prefix preprocessing.

25.39

Run all-pairs shortest paths once on the existing network. Then evaluate each proposed road $(x, y)$ by checking, for every city pair $(a, b)$ , whether routing through the new edge in either direction improves $S (a, b)$ . Each such test is $O (1)$ once the distance matrix is known, so the total is $O (n^{3} + k n^{2})$ .

25.40

Take logarithms: a product of exchange rates greater than 1 becomes a sum of negative edge weights after transforming each edge weight to $- lo g r$ . Therefore an arbitrage exists exactly when the transformed graph contains a negative cycle. Detect that with Bellman-Ford.

Takashi's Notes

Explorer

Honors Class

Honors Class

Problems

25.1

25.2

25.3

25.4

25.5

25.6

25.7

25.8

25.9

25.10

25.11

25.12

25.13

25.14

25.15

25.16

25.17

25.18

25.19

25.20

25.21

25.22

25.23

25.24

25.25

25.26

25.27

25.28

25.29

25.30

25.31

25.32

25.33

25.34

25.35

25.36

25.37

25.38

25.39

25.40

Answers

25.1

25.2

25.3

25.4

25.5

25.6

25.7

25.8

25.9

25.10

25.11

25.12

25.13

25.14

25.15

25.16

25.17

25.18

25.19

25.20

25.21

25.22

25.23

25.24

25.25

25.26

25.27

25.28

25.29

25.30

25.31

25.32

25.33

25.34