Official Analysis

Video Solution

By Abhiraj Mallangi

Note: The video solution might not be the same as other solutions. Code in C++ and Java.

Solution

Explanation

First, let's define some variables. Let $a_1, a_2, ..., a_n$ be the block sizes, sorted from least to greatest. Let $b_i$ be the number of indices $j$ such that $j < i$ and $a_i \leq a_j + d$. Let $\texttt{ans}_i$ be the answer if the tower consisted of only the blocks $a_1, a_2, ..., a_i$. Of course, this means that $\texttt{ans}_n$ will be the final answer.

For any tower consisting of the first $i - 1$ blocks, there will always be $b_i + 1$ number of ways to insert the block of size $a_i$ into the tower. To understand why, consider where the block of size $a_i$ can be inserted. The block of size $a_i$ can always be inserted at the bottom of the tower, because there is no block larger than $a_i$ in the tower. The block with size $a_i$ can be inserted at the top of some block $x$ with size $a_x$ if and only if $a_i \leq a_x + d$.

Thus, we see that $\texttt{ans}_i = \texttt{ans}_{i-1} \cdot (b_i + 1)$, because there are $b_i + 1$ valid ways to insert block $a_i$ into any of the $ans_{i-1}$ valid towers.

Implementation

This solution uses 2 pointers instead of creating the arrays $ans[]$ and $b[]$.

Time Complexity: $\mathcal{O}(N \log N)$

Copy
MOD = 10**9 + 9

n, d = map(int, input().split())
blocks = list(map(int, input().split()))

blocks.sort()  # sort the blocks

right = 0
res = 1
for left in range(n):