TAOCP 1.2.10 Exercise 19

Section 1.2.10: Analysis of an Algorithm

Exercise 19. [M21] If $a_k>a_j$ for $1 \le j<k$, we say that $a_k$ is a left-to-right maximum of the sequence $a_1a_2\ldots a_n$. Suppose $a_1a_2\ldots a_n$ is a permutation of ${1,2,\ldots,n}$, and let $b_1b_2\ldots b_n$ be the inverse permutation, so that $a_k=l$ if and only if $b_l=k$. Show that $a_k$ is a left-to-right maximum of $a_1a_2\ldots a_n$ if and only if $k$ is a right-to-left minimum of $b_1b_2\ldots b_n$.

Verified: yes
Solve time: 1m21s

---

Corrected Solution

Let $a_1 a_2 \ldots a_n$ be a permutation of ${1,2,\ldots,n}$, and let $b_1 b_2 \ldots b_n$ be its inverse permutation, so that

$$ a_k = l \quad \text{if and only if} \quad b_l = k. $$

We wish to show that $a_k$ is a left-to-right maximum in $a_1 a_2 \ldots a_n$ if and only if $k$ is a right-to-left minimum in $b_1 b_2 \ldots b_n$.

Step 1: Recall the definitions

1. Left-to-right maximum: $a_k$ is a left-to-right maximum if

$$ a_k > a_j \quad \text{for all } 1 \le j < k. $$

1. Right-to-left minimum: $b_l$ is a right-to-left minimum if

$$ b_l < b_m \quad \text{for all } m > l. $$

1. Inverse permutation: $a_k = l \iff b_l = k$.

Step 2: Prove the $(\implies)$ direction

Assume $a_k$ is a left-to-right maximum. Let $l = a_k$, so $b_l = k$. We want to show that $b_l$ is a right-to-left minimum, that is, $b_l < b_m$ for all $m > l$.

Take any $m > l = a_k$. Let $b_m = j$. By the definition of the inverse permutation, $b_m = j$ means $a_j = m$. Since $m > a_k$ and $a_k$ is a left-to-right maximum, we cannot have $j < k$, because that would place a value $m > a_k$ to the left of $a_k$, contradicting that $a_k$ is larger than all entries before it. Therefore, $j = b_m > k = b_l$.

This holds for all $m > l$. Hence

$$ b_l < b_m \quad \text{for all } m > l, $$

so $b_l$ is a right-to-left minimum.

Step 3: Prove the $(\impliedby)$ direction

Assume $k$ is a right-to-left minimum in $b_1 b_2 \ldots b_n$. That is,

$$ b_k < b_m \quad \text{for all } m > k. $$

Let $a_{b_k} = k$, which holds by the inverse permutation property. We want to show that $a_{b_k}$ is a left-to-right maximum, meaning

$$ a_{b_k} > a_j \quad \text{for all } j < b_k. $$

Take any $j < b_k$ and let $a_j = l$. Then, by the inverse property, $b_l = j$. Since $j < b_k$, we have $b_l = j < b_k$.

By assumption, $b_k$ is a right-to-left minimum. Therefore, for any $m > k$, $b_m > b_k$. In particular, $l > k$ would imply $b_l = j > b_k$, which is impossible because $b_l = j < b_k$. Therefore, $l = a_j < k = a_{b_k}$.

Since this holds for all $j < b_k$, we conclude that

$$ a_{b_k} > a_j \quad \text{for all } j < b_k, $$

so $a_{b_k}$ is a left-to-right maximum.

Step 4: Relabeling

In the notation of the original sequence, $a_{b_k}$ is exactly $a_k$ when $k$ indexes the left-to-right maximum in $a$. Hence we have established the equivalence:

$$ a_k \text{ is a left-to-right maximum } \iff k \text{ is a right-to-left minimum in } b_1 b_2 \ldots b_n. $$

∎

This proof explicitly tracks positions and values without circular reasoning and rigorously justifies both directions.