Find the N-th Value After K Seconds solution and explanation
6 more videos on this problem
3179. Find the N-th Value After K Seconds | Pascal's Triangle | DP | Bottom Up Optimised DPAryan Mittal · 7:51 · 1K views
3179 Find the N th Value After K Seconds || How to 🤔 in Interview || Dynamic Programming 🔥Ayush Rao · 6:26 · 577 views
Leetcode 3179: Find the N-th Value After K SecondsAlgorithms Casts · 13:00 · 200 views
3179. Find the N-th Value After K Seconds (Leetcode Medium)Programming Live with Larry · 5:08 · 141 views
Find the N-th Value After K Seconds | LeetCode weekly Contest 401Developer Coder · 4:45 · 136 views
LeetCode CONTEST 401 |Find the N-th Value After K Seconds | Leetcode 3179 | top MAANG Interview|JavaCode Thoughts · 5:55 · 92 views
LeetCode 3179 | Find the N-th Value After K Seconds | Weekly Contest 401 | Dynamic Programming | DSAAlgo Horizon · 10:12 · 80 views
The problem
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
Approach overview
Problem 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 1: Dynamic Programming
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.
def findNthValue(n, k):
MOD = 1000000007
a = [1] * n
for _ in range(k):
for i in range(1, n):
a[i] = (a[i] + a[i-1]) % MOD
return a[n-1]
print(findNthValue(4, 5))public class Solution {
static final int MOD = 1000000007;
public int findNthValue(int n, int k) {
int[] a = new int[n];
for (int i = 0; i < n; ++i) {
a[i] = 1;
}
for (int j = 0; j < k; ++j) {
for (int i = 1; i < n; ++i) {
a[i] = (a[i] + a[i-1]) % MOD;
}
}
return a[n - 1];
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findNthValue(4, 5));
}
}#include <iostream>
#include <vector>
#define MOD 1000000007
int findNthValue(int n, int k) {
std::vector<int> a(n, 1);
for (int j = 0; j < k; ++j) {
for (int i = 1; i < n; ++i) {
a[i] = (a[i] + a[i-1]) % MOD;
}
}
return a[n - 1];
}
int main() {
int n = 4, k = 5;
std::cout << findNthValue(n, k) << std::endl;
return 0;
}function findNthValue(n, k) {
const MOD = 1000000007;
let a = new Array(n).fill(1);
for (let j = 0; j < k; j++) {
for (let i = 1; i < n; i++) {
a[i] = (a[i] + a[i-1]) % MOD;
}
}
return a[n-1];
}
console.log(findNthValue(4, 5));#include <stdio.h>
#define MOD 1000000007
int findNthValue(int n, int k) {
int a[n];
for (int i = 0; i < n; ++i) {
a[i] = 1;
}
for (int j = 0; j < k; ++j) {
for (int i = 1; i < n; ++i) {
a[i] = (a[i] + a[i-1]) % MOD;
}
}
return a[n - 1];
}
int main() {
int n = 4, k = 5;
printf("%d\n", findNthValue(n, k));
return 0;
}using System;
public class Solution {
const int MOD = 1000000007;
public int FindNthValue(int n, int k) {
int[] a = new int[n];
for (int i = 0; i < n; i++) {
a[i] = 1;
}
for (int j = 0; j < k; j++) {
for (int i = 1; i < n; i++) {
a[i] = (a[i] + a[i-1]) % MOD;
}
}
return a[n - 1];
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.FindNthValue(4, 5));
}
}This Python function makes use of a list a to store the intermediate states of the array. We iterate over k seconds and update elements cumulatively. Each element is updated as the sum of itself and all the preceding elements, modulo 10^9 + 7.
Time Complexity: O(n * k)
Space Complexity: O(n)
Approach 2: Combinatorial Approach
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.
def factorial(n, MOD):
result = 1
for i in range(1, n + 1):
result = (result * i) % MOD
return result
def binomialCoeff(n, k, MOD):
if k > n - k:
k = n - k
num = factorial(n, MOD)
denom = (factorial(k, MOD) * factorial(n - k, MOD)) % MOD
return num * pow(denom, MOD - 2, MOD) % MOD
MOD = 1000000007
def findNthValue(n, k):
return binomialCoeff(n + k - 1, n - 1, MOD)
print(findNthValue(4, 5))public class Solution {
static final int MOD = 1000000007;
public long binomialCoeff(int n, int k) {
if (k > n - k) k = n - k;
long res = 1;
for (int i = 0; i < k; ++i) {
res = (res * (n - i) / (i + 1)) % MOD;
}
return res;
}
public int findNthValue(int n, int k) {
return (int) binomialCoeff(n + k - 1, n - 1);
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findNthValue(4, 5));
}
}#include <iostream>
#define MOD 1000000007
long long binomialCoeff(int n, int k, int MOD) {
if (k > n - k) k = n - k;
long long res = 1;
for (int i = 0; i < k; ++i) {
res *= (n - i);
res /= (i + 1);
res %= MOD;
}
return res;
}
int findNthValue(int n, int k) {
return binomialCoeff(n + k - 1, n - 1, MOD);
}
int main() {
std::cout << findNthValue(4, 5) << std::endl;
return 0;
}function binomialCoeff(n, k, MOD) {
if (k > n - k) k = n - k;
let res = 1;
for (let i = 0; i < k; i++) {
res = (res * (n - i)) / (i + 1);
res %= MOD;
}
return res;
}
function findNthValue(n, k) {
const MOD = 1000000007;
return binomialCoeff(n + k - 1, n - 1, MOD);
}
console.log(findNthValue(4, 5));#include <stdio.h>
#define MOD 1000000007
int combination(int n, int r, int MOD) {
if (r > n) return 0;
if (r == 0 || r == n) return 1;
r = r > (n / 2) ? n - r : r; // take advantage of symmetry
long long result = 1;
for (int k = 0; k < r; ++k) {
result = result * (n - k) / (k + 1);
result %= MOD;
}
return (int)result;
}
int findNthValue(int n, int k) {
return combination(n + k - 1, n - 1, MOD);
}
int main() {
printf("%d\n", findNthValue(4, 5));
return 0;
}using System;
public class Solution {
const int MOD = 1000000007;
static int BinomialCoeff(int n, int k) {
if (k > n - k) k = n - k;
long res = 1;
for (int i = 0; i < k; i++) {
res = (res * (n - i) / (i + 1)) % MOD;
}
return (int)res;
}
public int FindNthValue(int n, int k) {
return BinomialCoeff(n + k - 1, n - 1);
}
public static void Main() {
Solution sol = new Solution();
Console.WriteLine(sol.FindNthValue(4, 5));
}
}This Python solution realizes the combinatorial approach with modular arithmetic to calculate factorial combinations and inverses. The function binomialCoeff efficiently calculates C(n+k-1, n-1) using factorials and Fermat's Little Theorem for modular inverses.
Time Complexity: O(n + log(MOD)) for computing factorials and modular inverses. Space Complexity: O(1) due to minimal extra storage.
Approach 3: Simulation
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.
function valueAfterKSeconds(n: number, k: number): number {
const a: number[] = Array(n).fill(1);
const mod: number = 10 ** 9 + 7;
while (k--) {
for (let i = 1; i < n; ++i) {
a[i] = (a[i] + a[i - 1]) % mod;
}
}
return a[n - 1];
}func valueAfterKSeconds(n int, k int) int {
const mod int = 1e9 + 7
a := make([]int, n)
for i := range a {
a[i] = 1
}
for ; k > 0; k-- {
for i := 1; i < n; i++ {
a[i] = (a[i] + a[i-1]) % mod
}
}
return a[n-1]
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming | Time Complexity: O(n * k) |
| Combinatorial Approach | Time Complexity: O(n + log(MOD)) for computing factorials and modular inverses. Space Complexity: O(1) due to minimal extra storage. |
| Simulation | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Find the N-th Value After K Seconds easy or hard?
The problem is rated Medium because the straightforward simulation is easy but recognizing the combinatorial pattern requires deeper insight. Identifying that the result equals C(n + k - 1, k) is the key step that leads to the optimal solution.
Find the N-th Value After K Seconds Python/Java solution
The dynamic programming solution iterates k times and updates an array using prefix sums. The optimal Python or Java solution computes C(n + k - 1, k) using a multiplicative combination formula with modulo arithmetic to avoid overflow.
How to solve Find the N-th Value After K Seconds in O(n)?
Recognize that repeated prefix sum operations produce values matching Pascal’s triangle. The final value becomes the binomial coefficient C(n + k - 1, k). Computing this combination with a multiplicative formula gives an O(n) solution without simulating each second.
What is the best approach for Find the N-th Value After K Seconds?
The most efficient approach uses a combinatorial formula. The value at index n-1 after k seconds equals C(n + k - 1, k). This avoids simulating all k prefix updates and reduces the complexity to O(n) or O(k) depending on the combination calculation method.
Is Find the N-th Value After K Seconds asked at Google/Amazon/Meta?
Problems involving prefix accumulation and combinatorial patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants often test recognition of Pascal triangle patterns or converting dynamic programming transitions into mathematical formulas.
What data structure is used in Find the N-th Value After K Seconds?
The simulation approach uses a simple array to maintain running prefix sums. The optimized approach mainly relies on mathematical computation of binomial coefficients, so no advanced data structures are required.
What is the time complexity of Find the N-th Value After K Seconds?
The straightforward dynamic programming simulation runs in O(n * k) time because the array of size n is updated for k seconds. The optimized combinatorial solution computes a binomial coefficient and runs in O(n) or O(k) time with constant extra space.