Find the N-th Value After K Seconds

Medium
889.

Find the N-th Value After K Seconds

Find the N-th Value After K Seconds is a medium coding problem on arrays, math and prefix sum, asked in Amazon, Adobe and Zoho interviews.

An array a of length n starts as all 1s. Every second, simultaneously, each element becomes the sum of all elements up to and including itself: a[i] = a[0] + a[1] + … + a[i].

Return a[n-1] after k seconds, modulo 10^9 + 7.

Example 1

Input
n = 4, k = 5
Output
56
Explanation
The array goes [1,1,1,1] → [1,2,3,4] → [1,3,6,10] → … → [1,6,21,56].

Example 2

Input
n = 5, k = 3
Output
35

Example 3

Input
n = 1, k = 1000
Output
1
Explanation
A single element is always its own prefix sum.

Constraints

  • 1 <= n, k <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var valueAfterKSeconds = function(n, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find the N-th Value After K Seconds — Problem & Solution

Find the N-th Value After K Seconds solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find the N-th Value After K Seconds is a medium coding problem on arrays, math and prefix sum, asked in Amazon, Adobe and Zoho interviews.

Problem statement

An array a of length n starts as all 1s. Every second, simultaneously, each element becomes the sum of all elements up to and including itself: a[i] = a[0] + a[1] + … + a[i].

Return a[n-1] after k seconds, modulo 10^9 + 7.

Example 1

Input: n = 4, k = 5
Output: 56
Explanation: The array goes [1,1,1,1] → [1,2,3,4] → [1,3,6,10] → … → [1,6,21,56].

Example 2

Input: n = 5, k = 3
Output: 35

Example 3

Input: n = 1, k = 1000
Output: 1
Explanation: A single element is always its own prefix sum.

Constraints

  • 1 <= n, k <= 1000

Hints for Find the N-th Value After K Seconds

  1. Hint 1

    One second is exactly a prefix-sum pass over the array.

  2. Hint 2

    A left-to-right in-place sweep computes it correctly, because each position wants the already-updated value to its left.

  3. Hint 3

    At these sizes k passes of length n is fast enough; the closed form is a binomial coefficient.

How to solve Find the N-th Value After K Seconds

Each second is one prefix-sum pass. Sweeping left to right in place gives exactly the simultaneous update, because a[i]'s new value is the new a[i-1] plus the old a[i].

Approach

  1. Start with all 1s.
  2. Repeat k times: for i from 1 to n-1, set a[i] += a[i-1], reducing modulo 10^9 + 7.
  3. Return a[n-1].

Why it works

The new a[i] is the sum of the old a[0 … i], which equals the new a[i-1] (already the sum of the old a[0 … i-1]) plus the old a[i] — so the in-place left-to-right sweep is exact despite the update being 'simultaneous'. The values are the entries of Pascal's triangle, so a[n-1] after k seconds is C(n + k - 1, k), which is the closed-form shortcut.

Complexity

  • Time — O(n · k)
  • Space — O(n)

Pitfalls

  • Sweeping right to left would use stale values and give the wrong answer.
  • The numbers explode without the modulo — reduce at every addition.
  • n = 1 never changes, since there is nothing to its left.

Reference solution

Python

def valueAfterKSeconds(n: int, k: int) -> int:
    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]

Java

public static int valueAfterKSeconds(int n, int k) {
    final int MOD = 1000000007;
    int[] a = new int[n];
    Arrays.fill(a, 1);
    for (int t = 0; t < k; t++) {
        for (int i = 1; i < n; i++) a[i] = (a[i] + a[i - 1]) % MOD;
    }
    return a[n - 1];
}

C++

int valueAfterKSeconds(int n, int k) {
    const int MOD = 1000000007;
    vector<int> a(n, 1);
    for (int t = 0; t < k; t++) {
        for (int i = 1; i < n; i++) a[i] = (a[i] + a[i - 1]) % MOD;
    }
    return a[n - 1];
}

JavaScript

var valueAfterKSeconds = function(n, k) {
    var MOD = 1000000007;
    var a = [];
    for (var t = 0; t < n; t++) a.push(1);
    for (var s = 0; s < k; s++) {
        for (var i = 1; i < n; i++) a[i] = (a[i] + a[i - 1]) % MOD;
    }
    return a[n - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Prefix Sum