Find the N-th Value After K Seconds
MedPrompt
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 <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly simulates the process described in the problem. We maintain an array representing the state a at each second. We start with an array of n ones. Then, for k seconds, we repeatedly update the array by calculating the prefix sum of the current array.
Algorithm
- Define a constant
MODas10^9 + 7. - Create an integer array
aof sizen. - Initialize all elements of
ato1. - Loop
ktimes, representing the seconds from1tok. - Inside the loop, iterate from
i = 1ton-1:- Update
a[i]by adding the value of the preceding element:a[i] = (a[i] + a[i-1]) % MOD.
- Update
- After the loops complete, the value at
a[n-1]is the final answer.
Walkthrough
The most straightforward way to solve this problem is to follow the simulation step-by-step. We begin with an array a of size n, where every element is 1. The problem states that after each second, every element a[i] is updated to be the sum of all preceding elements plus itself. This is equivalent to calculating the prefix sum of the array.
We can perform this simulation for k seconds. In each second, we can update the array in-place. The new value of a[i] is the sum of the old values from a[0] to a[i]. This can be calculated more efficiently as new_a[i] = new_a[i-1] + old_a[i]. Since we iterate from left to right, a[i-1] will already hold its new value for the current second. Thus, the update rule simplifies to a[i] = a[i] + a[i-1] for i > 0.
We repeat this process k times. All additions are performed modulo 10^9 + 7 to prevent integer overflow. After k iterations, a[n-1] will hold the required value.
class Solution { public int valueAfterKSeconds(int n, int k) { int MOD = 1_000_000_007; int[] a = new int[n]; java.util.Arrays.fill(a, 1); // Simulate for k seconds for (int second = 0; second < k; second++) { // Update the array to its prefix sum for (int i = 1; i < n; i++) { a[i] = (a[i] + a[i-1]) % MOD; } } return a[n - 1]; }}Complexity
Time
O(k * n) - We have a nested loop. The outer loop runs `k` times, and the inner loop for calculating prefix sums runs `n-1` times.
Space
O(n) - We use an array of size `n` to store the values at each second.
Trade-offs
Pros
Simple to understand and implement as it directly models the problem statement.
Sufficiently efficient for the given constraints (
n, k <= 1000).
Cons
Less efficient than the mathematical approach, with a quadratic time complexity.
Might be too slow if the constraints on
norkwere larger.
Solutions
Solution
class Solution {public int valueAfterKSeconds(int n, int k) { final int mod = (int)1 e9 + 7; int[] a = new int[n]; Arrays.fill(a, 1); while (k-- > 0) { for (int i = 1; i < n; ++i) { a[i] = (a[i] + a[i - 1]) % mod; } } return a[n - 1]; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.