Finding Arrangements of Blocks With L Left Visible Blocks and R Right Visible Blocks

1. Introduction

In this tutorial, we’ll see how to compute the number of ways to arrange the $N$ blocks with $L$ visible blocks on the left and $R$ visible ones on the right.

2. Problem Description

There are $N$ uniquely-sized blocks whose heights are integers from $1$ to $N$ . How many ways to arrange the $\mathbf{N}$ blocks in a row such that exactly $\mathbf{L}$ blocks are visible from the left and $\mathbf{R}$ blocks are visible from the right?

A block is visible from the left if there are no longer blocks to the left of it. Similarly, a block is visible from the right if there are no longer blocks to the right of it.

For example, if we arrange $5$ blocks with $\{1, 3, 2, 5, 4\}$ , then the blocks with heights $1$ , $3$ , and $5$ are visible from the left. Also, blocks with heights $4$ and $5$ are visible from the right:

The longest block with the height of $5$ is visible from both sides.

3. Solve the Left Part

Let’s first consider the left part only. Given $N$ blocks, let $f(N, L)$ denote the number of ways to arrange them with $L$ visible blocks from the left. We can divide this problem into two cases.

For the first case, we place the longest block in the end. In this way, the longest block is always visible from the left no matter how we arrange the rest $N-1$ blocks. Therefore, the problem becomes to solve $\mathbf{f(N-1, L-1)}$ as we need to find the number of ways to arrange the remaining $\mathbf{N-1}$ blocks with $\mathbf{L-1}$ visible ones:

For the second case, we place any block other than the longest one in the end. Since the longest block is not at the end position, it hides any blocks right after it, including the last one. Therefore, we should not count the last block as the visible block from the left. To make $L$ visible blocks from the left, we have to arrange them on the remaining $N-1$ blocks. Therefore, the problem becomes to solve $\mathbf{f(N-1, L)}$ to arrange the remaining $\mathbf{N-1}$ blocks with $\mathbf{L}$ visible ones:

Since we have $N-1$ possible ways to put a short block into the last position, the total number of ways for the second case is $(N-1) f(N-1, L)$ .

Based on the above observations, we can have our recurrence formula:

For the base case, if we have only one block, then there is only one way to see it visible from the left. Therefore, we can have $f(1, 1) = 1$ . Also, we have $f(1, k) = 0$ for $k > 1$ .

We can use a dynamic programming approach to compute the $\mathbf{f(N,L)}$ :

This algorithm uses a two-dimensional array, $dp$ , to compute the $f(N, L)$ . The array has $N+1$ rows and $L+1$ columns, as the array index starts from $0$ . We use this array to store the computed $f(N, L)$ values. When we compute $f(N, L)$ with bigger $N$ and $L$ , we can reuse the previously computed results from the smaller numbers.

Firstly, we store the base case, $f(1, 1) = 1$ , into the $dp$ array. Then, we use nested loops to go through all possible $N$ and $L$ values and compute $f(N, L)$ based on our recurrence formula. After we finish the computing, $dp[N][L]$ is the result we want.

Since we have two nested loops over the numbers $N$ and $L$ , the overall time complexity of this algorithm is $O(NL)$ .

4. S0lve Both Parts

Let’s consider an arrangement that contains $L$ visible blocks from the left and $R$ visible blocks from the right. For each visible block, we treat this block and all blocks between it and the next visible block as a whole segment. The longest block is a segment that contains itself only. Also, it is visible from both sides. Therefore, there are $\mathbf{L-1}$ segments before the longest block segment and $\mathbf{R-1}$ segments after the longest block segments:

For each segment on the right side, we can reverse the order of the blocks and move the whole segment to the left side. This makes $(L+R-2)$ segments before the longest block. Also, we can sort these segments based on the highest block in each segment. In this way, we can have $\mathbf{(L+R-2)}$ visible blocks to the left of the longest block:

Similarly, given a block arrangement where the longest block is at the last position and there are $(L+R-2)$ visible blocks from the left, we can pick $R-1$ segments and move them to the right of the longest block. In this way, we can have a block arrangement that contains $L$ visible blocks from the left and $R$ visible blocks from the right.

Therefore, we can reduce the original problem to a smaller problem that computes the arrangement where the longest block is at the end position and there are $\mathbf{L+R-2}$ visible blocks among the rest $\mathbf{N-1}$ blocks, which is $\mathbf{f(N-1, L+R-2)}$ .

Also, among the $L+R-2$ segments, we can choose any $R-1$ segments and move them to the right. Therefore, the overall number of possible ways is ${ (L+R-2) \choose (R-1)} f(N-1, L+R-2)$ , which is also $\frac{(L+R-2)!}{(L-1)!(R-1)!}f(N-1, L+R-2)$ .

We can use a factorial function and the previous $arrangeBlocksLeft$ function to calculate our result:

The time complexity for the factorial functions is $O(L+R)$ . Also, the $arrangeBlocksLeft$ function takes $O((L+R) N)$ time. Therefore, the overall time complexity of this algorithm is $O((L+R) N)$

5. Conclusion

In this tutorial, we showed a dynamic programming algorithm to compute the number of arrangements for $N$ blocks with $L$ visible blocks from the left. Based on this algorithm, we can extend to compute the number of arrangements for $N$ blocks with $L$ visible blocks from the left and $R$ visible blocks from the right.

Full Archive

About Baeldung

Core Concepts

Operating Systems

Artificial Intelligence

Graph Theory

Latex

1. Introduction

2. Problem Description

3. Solve the Left Part

4. S0lve Both Parts

5. Conclusion