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 <= 1000We 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.
C++
Java
Python
C#
JavaScript
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).
C++
Java
Python
C#
JavaScript
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).
| 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). |
Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 331,616 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