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

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]…

Difficulty: Medium
Topics: Arrays, Math, Simulation, Prefix Sum, Combinatorics
Asked at: Amazon, Adobe, Zoho
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

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

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

Start with all 1s.
Repeat k times: for i from 1 to n-1, set a[i] += a[i-1], reducing modulo 10^9 + 7.
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]

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#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue