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.
We can leverage dynamic programming to solve this problem efficiently. We use a 1D array to store the state of the array after each iteration. The key observation here is that the update to each element of the array can be seen as accumulating the previous values. Therefore, for the ith position after the jth second, we sum up the current and the previous values using the property that each a[i] is effectively a prefix sum of the initial state.
We use a dynamic programming approach where we iterate over the array and update the values by summing them cumulatively.
This solution uses an array a initialized to 1s. At each second, we update each element in the array to be the sum of all its preceding elements plus itself. This is done by iterating from the second element to the last, updating the elements in a cumulative fashion. The use of modulo 10^9 + 7 ensures we never deal with overly large numbers.
The time complexity of this solution is O(n * k) because we iterate over the array n for k seconds. The space complexity is O(n) for storing the array.
This approach utilizes combinatorial mathematics to solve the problem with an efficient calculation instead of iterative simulations. The observation is that each element a[i] after k seconds corresponds to the binomial coefficient C(k + i, i). The solution can be computed using properties of Pascal's Triangle and combinatorial numbers to directly calculate the value of a[n - 1] using properties that skip some steps, given the constraints of large k.
This C function calculates the binomial coefficient directly with a symmetry optimization to avoid large intermediary numbers that may affect performance. This allows for an efficient calculation of the a[n-1] value by finding the binomial coefficient C(n+k-1, n-1).
Using this direct calculation approach reduces the time complexity to approximately O(min(k, n)) due to optimized calculations with symmetry, and maintains space usage at O(1).
We notice that the range of the integer n is 1 leq n leq 1000, so we can directly simulate this process.
We define an array a of length n and initialize all elements to 1. Then we simulate the process for k seconds, updating the elements of array a every second until k seconds have passed.
Finally, we return a[n - 1].
The time complexity is O(n times k), and the space complexity is O(n). Where n is the length of the array a.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Dynamic Programming | The time complexity of this solution is O(n * k) because we iterate over the array n for k seconds. The space complexity is O(n) for storing the array. |
| Combinatorial Approach | Using this direct calculation approach reduces the time complexity to approximately O(min(k, n)) due to optimized calculations with symmetry, and maintains space usage at O(1). |
| Simulation | — |
| 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 |
3179. Find the N-th Value After K Seconds | Pascal's Triangle | DP | Bottom Up Optimised DP • Aryan Mittal • 1,636 views views
Watch 9 more video solutions →Practice Find the N-th Value After K Seconds with our built-in code editor and test cases.
Practice on FleetCode