Arrays

Problems

6.1

The quicksort algorithm proceeds recursively: it selects an element, the pivot, and reorders the array so that elements less than or equal to the pivot appear first, followed by elements greater than the pivot. With many duplicates, it is better to partition into three groups: less than the pivot, equal to the pivot, and greater than the pivot.

Write a program that takes an array $A$ and an index $i$ into $A$ , and rearranges the elements so that all elements less than $A [i]$ appear first, followed by elements equal to the pivot, followed by elements greater than the pivot.

Hint: Think about the partition step in quicksort.

Variant: Assuming keys take one of three values, reorder the array so that all objects with the same key appear together. The order of the subarrays is not important. Use $O (1)$ additional space and $O (n)$ time.

Variant: Given an array $A$ of $n$ objects with keys taking one of four values, reorder the array so that all objects with the same key appear together. Use $O (1)$ additional space and $O (n)$ time.

Variant: Given an array $A$ of objects with Boolean-valued keys, reorder the array so that objects with key false appear first. Use $O (1)$ additional space and $O (n)$ time.

Variant: Same as the previous variant, but preserve the relative ordering of the objects with key true. Use $O (1)$ additional space and $O (n)$ time.

6.2

Write a program which takes as input an array of digits encoding a decimal number $D$ and updates the array to represent the number $D + 1$ . For example, if the input is $⟨ 1, 2, 9 ⟩$ , update the array to $⟨ 1, 3, 0 ⟩$ . Your algorithm should work even if implemented in a language with finite-precision arithmetic.

Hint: Experiment with concrete examples.

Variant: Write a program which takes as input two strings $s$ and $t$ of bits encoding binary numbers $B_{s}$ and $B_{t}$ , respectively, and returns a new string of bits representing the number $B_{s} + B_{t}$ .

6.3

Applications sometimes require arbitrary-precision arithmetic using arrays of digits. Use one digit per array entry, with the most significant digit first, and use a negative leading digit to denote a negative integer. For example, $⟨ 1, 9, 3, 7, 0, 7, 7, 2, 1 ⟩$ represents $193707721$ , and $⟨ - 7, 6, 1, 8, 3, 8, 2, 5, 7, 2, 8, 7 ⟩$ represents $- 761838257287$ .

Write a program that takes two arrays representing integers and returns an integer representing their product. For example, since $193707721 \times - 761838257287 = - 147573952589676412927$ , if the inputs are $⟨ 1, 9, 3, 7, 0, 7, 7, 2, 1 ⟩$ and $⟨ - 7, 6, 1, 8, 3, 8, 2, 5, 7, 2, 8, 7 ⟩$ , your function should return $⟨ - 1, 4, 7, 5, 7, 3, 9, 5, 2, 5, 8, 9, 6, 7, 6, 4, 1, 2, 9, 2, 7 ⟩$ .

Hint: Use arrays to simulate the grade-school multiplication algorithm.

6.4

In a board game, each position has a nonnegative integer that gives the maximum you can advance from that position in one move. You begin at the first position and win by reaching the last position. For example, $A = ⟨ 3, 3, 1, 0, 2, 0, 1 ⟩$ can be won by going from $A [0]$ to $A [1]$ , then to $A [4]$ , then to $A [6]$ . In contrast, if $A = ⟨ 3, 2, 0, 0, 2, 0, 1 ⟩$ , the game cannot be won.

Write a program which takes an array $A$ of $n$ integers, where $A [i]$ denotes the maximum you can advance from index $i$ , and returns whether it is possible to advance to the last index starting from the beginning of the array.

Hint: Analyze each location, starting from the beginning.

Variant: Write a program to compute the minimum number of steps needed to advance to the last location.

6.5

This problem concerns deleting repeated elements from a sorted array. For example, if the array is $⟨ 2, 3, 5, 5, 7, 11, 11, 11, 13 ⟩$ , then after deletion, the array is $⟨ 2, 3, 5, 7, 11, 13, 0, 0, 0 ⟩$ . After deleting repeated elements, there are 6 valid entries. There are no requirements on the values stored beyond the last valid element.

Write a program which takes as input a sorted array and updates it so that all duplicates have been removed and the remaining elements have been shifted left to fill the emptied indices. Return the number of valid elements. Do not use library routines that directly perform this operation.

Hint: There is an $O (n)$ time and $O (1)$ space solution.

Variant: Implement a function which takes as input an array and a key, and updates the array so that all occurrences of the input key have been removed and the remaining elements have been shifted left to fill the emptied indices. Return the number of remaining elements.

Variant: Write a program which takes as input a sorted array $A$ of integers and a positive integer $m$ , and updates $A$ so that if $x$ appears $m$ times in $A$ it appears exactly $min (2, m)$ times in $A$ . Perform the update in one pass, and allocate no additional storage.

6.6

This problem concerns optimally buying and selling a stock once. For example, for prices $⟨ 310, 315, 275, 295, 260, 270, 290, 230, 255, 250 ⟩$ , the maximum profit is 30, achieved by buying at 260 and selling at 290. Note that 260 is not the lowest price, and 290 is not the highest price.

Write a program that takes an array denoting daily stock prices, and returns the maximum profit that could be made by buying and then selling one share of the stock.

Hint: Identifying the minimum and maximum is not enough, since the minimum may appear after the maximum.

Variant: Write a program that takes an array of integers and finds the length of a longest subarray all of whose entries are equal.

6.7

The max-difference problem asks for the maximum profit that can be made by buying and then selling a single share over a day range.

Write a program that computes the maximum profit that can be made by buying and selling a share at most twice. The second buy must be made on another date after the first sale.

Hint: What do you need to know about the first $i$ elements when processing the $(i + 1)$ th element?

Variant: Solve the same problem in $O (n)$ time and $O (1)$ space.

6.8

A natural number is called prime if it is bigger than 1 and has no divisors other than 1 and itself.

Write a program that takes an integer argument and returns all the primes between 1 and that integer. For example, if the input is 18, return $⟨ 2, 3, 5, 7, 11, 13, 17 ⟩$ .

Hint: Exclude the multiples of primes.

6.9

A permutation can be specified by an array $P$ , where $P [i]$ represents the destination of the element at index $i$ . For example, $⟨ 2, 0, 1, 3 ⟩$ maps the element at location 0 to location 2, the element at location 1 to location 0, the element at location 2 to location 1, and leaves the element at location 3 unchanged. Applied to $A = ⟨ a, b, c, d ⟩$ , the result is $⟨ b, c, a, d ⟩$ .

Given an array $A$ of $n$ elements and a permutation $P$ , apply $P$ to $A$ .

Hint: Any permutation can be viewed as a set of cyclic permutations. For an element in a cycle, how would you identify if it has been permuted?

Variant: Given an array $A$ of integers representing a permutation, update $A$ to represent the inverse permutation using only constant additional storage.

6.10

There are exactly $n!$ permutations of $n$ elements. They can be totally ordered using dictionary ordering: permutation $p$ appears before permutation $q$ if, at the first position where they differ, the corresponding entry for $p$ is less than that for $q$ . For example, $⟨ 2, 0, 1 ⟩ < ⟨ 2, 1, 0 ⟩$ . The permutation $⟨ 0, 1, 2 ⟩$ is the smallest, and $⟨ 2, 1, 0 ⟩$ is the largest.

Write a program that takes as input a permutation, and returns the next permutation under dictionary ordering. If the permutation is the last permutation, return the empty array. For example, if the input is $⟨ 1, 0, 3, 2 ⟩$ your function should return $⟨ 1, 2, 0, 3 ⟩$ . If the input is $⟨ 3, 2, 1, 0 ⟩$ , return $⟨ ⟩$ .

Hint: Study concrete examples.

Variant: Compute the $k$ th permutation under dictionary ordering, starting from the identity permutation.

Variant: Given a permutation $p$ , return the permutation corresponding to the previous permutation of $p$ under dictionary ordering.

6.11

This problem is motivated by the need for a company to select a random subset of its customers to roll out a new feature.

Implement an algorithm that takes as input an array of distinct elements and a size, and returns a subset of the given size of the array elements. All subsets should be equally likely. Return the result in the input array itself.

Hint: How would you construct a random subset of size $k + 1$ given a random subset of size $k$ ?

Variant: The rand() function in the standard C library returns a uniformly random number in $[0, RAND_MAX - 1]$ . Does $rand () mod n$ generate a number uniformly distributed in $[0, n - 1]$ ?

6.12

This problem is motivated by the design of a packet sniffer that provides a uniform sample of packets for a network session.

Design a program that takes as input a size $k$ , and reads packets continuously, maintaining a uniform random subset of size $k$ of the read packets.

Hint: Suppose you have a procedure which selects $k$ packets from the first $n \geq k$ packets as specified. How would you deal with the $(n + 1)$ th packet?

6.13

Generating random permutations is subtler than it looks. For example, iterating through $⟨ 0, 1, \dots, n - 1 ⟩$ and swapping each element with another randomly selected element does not generate all permutations with equal probability. For $n = 3$ , there are 6 permutations, but this flawed procedure has $3^{3} = 27$ equally likely execution paths, so some permutations occur more often than others.

Design an algorithm that creates uniformly random permutations of $⟨ 0, 1, \dots, n - 1 ⟩$ . You are given a random number generator that returns integers in ${0, 1, \dots, n - 1}$ with equal probability; use as few calls to it as possible.

Hint: If the result is stored in $A$ , how would you proceed once $A [n - 1]$ is assigned correctly?

6.14

The set ${0, 1, 2, \dots, n - 1}$ has $(k n) = n! / ((n - k)! k!)$ subsets of size $k$ . Return any one of these size- $k$ subsets with equal probability.

Write a program that takes as input a positive integer $n$ and a size $k \leq n$ , and returns a size- $k$ subset of ${0, 1, 2, \dots, n - 1}$ . Represent the subset as an array. All subsets should be equally likely and, in addition, all permutations of the elements of the array should be equally likely. You may assume you have a function which takes as input a nonnegative integer $t$ and returns an integer in the set ${0, 1, \dots, t - 1}$ with uniform probability.

Hint: Simulate Problem 6.11, using an appropriate data structure to reduce space.

6.15

Suppose you need to write a load test for a server. You studied the inter-arrival times of requests over a year and computed a histogram of the distribution. You want to generate synthetic requests whose inter-arrival times follow the same distribution.

You are given $n$ numbers as well as probabilities $p_{0}, p_{1}, \dots, p_{n - 1}$ , which sum to 1. Given a random number generator that produces values in $[0, 1]$ uniformly, how would you generate one of the $n$ numbers according to the specified probabilities? For example, if the numbers are 3, 5, 7, 11, and the probabilities are $9/18, 6/18, 2/18, 1/18$ , then in 1,000,000 calls, 3 should appear roughly 500,000 times, 5 should appear roughly 333,333 times, 7 roughly 111,111 times, and 11 roughly 55,555 times.

Hint: Look at the graph of the probability that the selected number is less than or equal to $α$ . What do the jumps correspond to?

Variant: Given a random number generator that produces values in $[0, 1]$ uniformly, how would you generate a value $X$ from $T$ according to a continuous probability distribution, such as the exponential distribution?

6.16

Sudoku is a popular logic-based combinatorial number-placement puzzle. The objective is to fill a $9 \times 9$ grid with digits subject to the constraint that each column, each row, and each of the nine $3 \times 3$ sub-grids contains unique integers in $[1, 9]$ . A partially completed puzzle uses 0 to denote a blank entry.

Check whether a $9 \times 9$ 2D array representing a partially completed Sudoku is valid. Specifically, check that no row, column, or $3 \times 3$ 2D subarray contains duplicates.

Hint: Directly test the constraints. Use an array to encode sets.

6.17

A 2D array can be written as a sequence in several orders, such as row-by-row or column-by-column. In this problem, write the array in spiral order. For the $3 \times 3$ array in Figure 6.3(a), the spiral order is $⟨ 1, 2, 3, 6, 9, 8, 7, 4, 5 ⟩$ . For Figure 6.3(b), it is $⟨ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10 ⟩$ .

Write a program which takes an $n \times n$ 2D array and returns the spiral ordering of the array.

Hint: Use case analysis and divide-and-conquer.

Variant: Given a dimension $d$ , generate a $d \times d$ 2D array whose spiral order is $⟨ 1, 2, 3, \dots, d^{2} ⟩$ . For example, if $d = 3$ , the result should be

187296345

Variant: Given a sequence of integers $P$ , compute a 2D array $A$ whose spiral order is $P$ . Assume the size of $P$ is $n^{2}$ for some integer $n$ .

Variant: Write a program to enumerate the first $n$ pairs of integers $(a, b)$ in spiral order, starting from $(0, 0)$ followed by $(1, 0)$ . For example, if $n = 10$ , output $(0, 0), (1, 0), (1, - 1), (0, - 1), (- 1, - 1), (- 1, 0), (0, 1), (1, 1), (2, 1)$ .

Variant: Compute the spiral order for an $m \times n$ 2D array $A$ .

Variant: Compute the last element in spiral order for an $m \times n$ 2D array $A$ in $O (1)$ time.

Variant: Compute the $k$ th element in spiral order for an $m \times n$ 2D array $A$ in $O (1)$ time.

6.18

Image rotation is a fundamental operation in computer graphics. In this problem, a 2D array represents a bitmap of an image, and the image is rotated by 90 degrees clockwise.

Write a function that takes as input an $n \times n$ 2D array, and rotates the array by 90 degrees clockwise.

Hint: Focus on the boundary elements.

Variant: Implement an algorithm to reflect $A$ , assumed to be an $n \times n$ 2D array, about the horizontal axis of symmetry. Repeat the same for reflections about the vertical axis, the diagonal from top-left to bottom-right, and the diagonal from top-right to bottom-left.

6.19

Figure 6.5 shows the first five rows of Pascal’s triangle. Each row contains one more entry than the previous one. Except for entries in the last row, each entry is adjacent to one or two numbers in the row below it. The first row holds 1. Each entry holds the sum of the numbers in the adjacent entries above it.

Write a program which takes as input a nonnegative integer $n$ and returns the first $n$ rows of Pascal’s triangle.

Hint: Write the given fact as an equation.

Variant: Compute the $n$ th row of Pascal’s triangle using $O (n)$ space.

Answers

6.1

Maintain four regions: elements less than the pivot, elements equal to the pivot, unclassified elements, and elements greater than the pivot. Scan through the unclassified region and swap each incoming element into the correct region. This is the classic Dutch-national-flag partition and runs in $O (n)$ time with $O (1)$ extra space.

6.2

Increment the last digit, then propagate carries from right to left. If the most significant digit overflows to 10, replace it with 0 and prepend 1. This works directly on the digit array, avoids integer overflow, and runs in $O (n)$ time.

6.3

Simulate grade-school multiplication on arrays of digits. Normalize the signs first, use an output array of length $n + m$ , accumulate per-digit products into the correct positions, propagate carries, strip leading zeroes, and restore the sign. The running time is $O (nm)$ .

6.4

Track the furthest reachable index while scanning left to right. At position $i$ , update the furthest reachable point to $max (furthest, i + A [i])$ . If you ever reach an index beyond the current furthest reachable point, the end is impossible; if the furthest reachable point reaches the last index, succeed. This is $O (n)$ time and $O (1)$ space.

6.5

Because the input is sorted, duplicates are consecutive. Keep a write index for the next valid slot, scan once from left to right, and copy a value forward only when it differs from the previously written value. Return the final write index as the number of valid entries. This is $O (n)$ time and $O (1)$ space.

6.6

Track the minimum price seen so far and, for each day, compute the profit from selling that day after buying at that minimum. Keep the maximum such profit over the scan. This is $O (n)$ time and $O (1)$ space.

6.7

Do a forward pass computing the best single-buy/single-sell profit ending at or before each day. Then do a backward pass computing the best second transaction starting at or after each day, and combine the two. The chapter solution uses an auxiliary array and runs in $O (n)$ time and $O (n)$ space. The $O (1)$ -space variant folds the same state into a constant number of running values.

6.8

Use sieving instead of independent primality tests. Maintain a Boolean candidate array, mark off multiples of each prime, and collect the survivors. The improved version starts crossing off at $p^{2}$ and skips even numbers. This yields the usual sieve behavior: $O (n lo g lo g n)$ time and $O (n)$ space.

6.9

Decompose the permutation into disjoint cycles and rotate each cycle in place. One way to avoid extra storage is to mark entries of the permutation array as processed by subtracting $n$ , then restore the permutation afterward. That gives $O (n)$ time and $O (1)$ extra space if temporary mutation of the permutation is allowed.

6.10

Find the longest decreasing suffix. If the entire permutation is decreasing, there is no next permutation. Otherwise:

Find the pivot $k$ just before the suffix, where $p [k] < p [k + 1]$ .
Find the smallest suffix entry larger than $p [k]$ .
Swap it with $p [k]$ .
Reverse the suffix.

This makes the smallest possible increase and runs in $O (n)$ time with $O (1)$ space.

6.11

Construct the subset incrementally in place. For position $i$ from 0 to $k - 1$ , choose a random index in $[i, n - 1]$ and swap that entry into position $i$ . After $k$ iterations, the first $k$ entries form a uniformly random subset. This is $O (k)$ time and $O (1)$ extra space.

6.12

Use reservoir sampling. Keep the first $k$ packets. When the $(n + 1)$ th packet arrives, include it in the sample with probability $k / (n + 1)$ ; if included, replace a uniformly random existing sample entry. This maintains a uniform sample of size $k$ over the entire stream, with $O (1)$ work per packet and $O (k)$ space.

6.13

Generate the permutation by sampling in place from shrinking suffixes: for $i = 0.. n - 1$ , choose a random index in $[i, n - 1]$ and swap it into position $i$ . This is the Fisher-Yates shuffle. It produces every permutation with equal probability in $O (n)$ time and uses no storage beyond the permutation array itself.

6.14

Simulate the in-place sampling idea from Problem 6.11 without materializing the full array $0.. n - 1$ . Store only the positions whose values differ from their defaults in a hash table. Each step randomly selects an index in the remaining range and updates the hash table as though a swap had occurred in the conceptual array. Because only $k$ positions are touched, the algorithm runs in $O (k)$ expected time and uses $O (k)$ space.

6.15

Build prefix sums of the probabilities:

$0, p_{0}, p_{0} + p_{1}, \dots, p_{0} + p_{1} + \dots + p_{n - 1}$ .

Draw a uniform random number in $[0, 1]$ and binary-search for the interval containing it. Return the value associated with that interval. Building the prefix array is $O (n)$ time and space; each subsequent sample is $O (lo g n)$ .

6.16

Check every row, every column, and every $3 \times 3$ subgrid for duplicates among the nonzero entries. The clean implementation uses a small Boolean array or bitset to represent which digits have appeared while checking a region. For an $n \times n$ Sudoku with $n \times n$ boxes, the time is $O (n^{2})$ and the auxiliary space is $O (n)$ .

6.17

Process the matrix layer by layer from the outside in. For each layer, append the top row, right column, bottom row in reverse, and left column in reverse; handle the center separately when $n$ is odd. That gives $O (n^{2})$ time and $O (1)$ extra space beyond the output. The chapter also presents a directional simulation that walks right, down, left, and up while marking visited entries.

6.18

Rotate the matrix in place, layer by layer. Within each layer, perform a four-way swap for corresponding boundary elements:

top goes to right
right goes to bottom
bottom goes to left
left goes to top

Processing all layers gives $O (n^{2})$ time and $O (1)$ extra space.

6.19

Build Pascal’s triangle row by row. In row $i$ , the endpoints are 1, and each interior entry is the sum of the two entries above it from the previous row. Since there are $1 + 2 + \dots + n = O (n^{2})$ total entries across the first $n$ rows, both time and space are $O (n^{2})$ . The $O (n)$ -space variant computes one row at a time.

Takashi's Notes

Explorer

Arrays

Arrays

Problems

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

6.9

6.10

6.11

6.12

6.13

6.14

6.15

6.16

6.17

6.18

6.19

Answers

6.1

6.2

6.3

6.4

6.5

6.6

6.7

6.8

6.9

6.10

6.11

6.12

6.13

6.14

6.15

6.16

6.17

6.18

6.19

Graph View

Table of Contents

Backlinks