Find the N-th Value After K Seconds

Find the N-th Value After K Seconds

What is this problem about?

In the Find the N-th Value After K Seconds coding problem, you have an array of $n$ elements, all initially 1. Every second, each element $a[i]$ is updated to be the sum of all elements from $a[0]$ to $a[i]$ from the previous second. You need to return the value of the $n$-th element after $k$ seconds, modulo $10^9 + 7$.

Why is this asked in interviews?

Walmart Labs uses this to test whether you can move from Simulation to Combinatorics. While you can simulate the process in $O(N imes K)$, if $N$ and $K$ are large, you need a mathematical solution. This problem is an application of Pascal's Triangle properties and Stars and Bars. It evaluations your ability to recognize that the $i$-th element after $j$ seconds is a binomial coefficient.

Algorithmic pattern used

There are two ways to solve this:

1. Simulation ($O(N imes K)$): Maintain a prefix sum array and update it $k$ times.
2. Combinatorics ($O(N + K)$): The updates describe a process where the $j$-th element in the $i$-th row of Pascal's triangle is being calculated. Specifically, the $n$-th value after $k$ seconds corresponds to the binomial coefficient $\binom{n+k-1}{k}$.

Example explanation

$n = 3, k = 2$

1. Initial: [1, 1, 1]
2. Sec 1: [1, 1+1, 1+1+1] $o$ [1, 2, 3]
3. Sec 2: [1, 1+2, 1+2+3] $o$ [1, 3, 6] Result: 6. Using formula: $\binom{3+2-1}{2} = \binom{4}{2} = \frac{4 imes 3}{2} = 6$.

Common mistakes candidates make

• Modulo arithmetic: Forgetting to take the modulo at each addition in the simulation.
• Combinatorial overflow: Not using modular inverse for the division when calculating combinations with large factorials.
• Complexity: Attempting $O(N imes K)$ when the problem constraints require $O(N+K)$.

Interview preparation tip

Problems involving "running sums of running sums" are almost always related to Binomial Coefficients or the diagonals of Pascal's Triangle. If you see this pattern, try to map the steps to the $\binom{n+k-1}{k}$ formula.