Watch 10 video solutions for Find the N-th Value After K Seconds, a medium level problem involving Array, Math, Simulation. This walkthrough by Aryan Mittal has 1,636 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
You are given two integers n and k.
Initially, you start with an array a of n integers where a[i] = 1 for all 0 <= i <= n - 1. After each second, you simultaneously update each element to be the sum of all its preceding elements plus the element itself. For example, after one second, a[0] remains the same, a[1] becomes a[0] + a[1], a[2] becomes a[0] + a[1] + a[2], and so on.
Return the value of a[n - 1] after k seconds.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: n = 4, k = 5
Output: 56
Explanation:
| Second | State After |
|---|---|
| 0 | [1,1,1,1] |
| 1 | [1,2,3,4] |
| 2 | [1,3,6,10] |
| 3 | [1,4,10,20] |
| 4 | [1,5,15,35] |
| 5 | [1,6,21,56] |
Example 2:
Input: n = 5, k = 3
Output: 35
Explanation:
| Second | State After |
|---|---|
| 0 | [1,1,1,1,1] |
| 1 | [1,2,3,4,5] |
| 2 | [1,3,6,10,15] |
| 3 | [1,4,10,20,35] |
Constraints:
1 <= n, k <= 1000Problem Overview: You start with an array of length n filled with 1s. Every second, each element becomes the sum of itself and all previous elements. After performing this operation k times, return the value at index n - 1. The repeated prefix accumulation turns the array into a combinatorial growth pattern.
Approach 1: Dynamic Programming / Prefix Simulation (Time: O(n * k), Space: O(n))
Simulate the process exactly as described. Maintain an array of size n initialized with 1s. For each of the k seconds, update the array so that a[i] = a[i] + a[i-1]. Iterating from left to right naturally builds the running prefix sum. After k iterations, the last element holds the required value.
The key observation is that each step converts the array into its prefix sum representation. This directly mirrors the operation described in the problem. The approach is easy to implement and avoids extra structures. Because you repeat the prefix update k times across n elements, the total time complexity is O(nk). Space stays O(n) since only one array is maintained.
This method heavily relies on the concept of prefix sum accumulation and fits well when constraints are small enough for simulation.
Approach 2: Combinatorial Insight (Time: O(n) or O(k), Space: O(1))
The repeated prefix operation forms Pascal-like layers. After analyzing small examples, the value at position n-1 after k seconds equals the binomial coefficient C(n + k - 1, k). Each update step effectively counts the number of ways contributions from earlier indices propagate forward.
This turns the simulation problem into a direct combinatorics calculation. Instead of updating the array repeatedly, compute the combination using the multiplicative formula or factorials with modular arithmetic. The result is obtained in linear time relative to k (or n) with constant extra space.
This approach leverages properties from combinatorics and patterns similar to Pascal’s triangle often seen in dynamic programming transitions. It avoids the n × k simulation cost and scales much better when both parameters are large.
Recommended for interviews: Start with the dynamic programming simulation to demonstrate understanding of the prefix update process. Then point out the pattern that leads to the binomial coefficient C(n + k - 1, k). Interviewers usually expect the combinatorial optimization because it reduces the complexity significantly and shows strong pattern recognition.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming / Prefix Simulation | O(n * k) | O(n) | Best for understanding the process directly or when constraints are small |
| Combinatorial Formula (Binomial Coefficient) | O(n) or O(k) | O(1) | Preferred for large inputs and optimal interview solution |