Find the N-th Value After K Seconds

Medium Dynamic Programming 2D DP Original on LeetCode

Find the N-th Value After K Seconds is a medium dynamic programming problem solved with the 2d dp pattern. The best approach, optimal (binomial coefficient), runs in O(k + log p) time and O(1) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from simulation (prefix sums) up.

Problem

Start with an array a of n ones. Every second, all elements change at the same moment: each a[i] becomes the sum of the elements a[0] through a[i] as they were before that second.

After k seconds, return the value of the last element a[n - 1]. Because it can be huge, return it modulo 10^9 + 7.

Examples

Example 1

Input
n = 3, k = 2
Output
6
Why
[1, 1, 1] becomes [1, 2, 3] after one second and [1, 3, 6] after two.

Example 2

Input
n = 1, k = 5
Output
1
Why
A single element is always its own prefix sum, so it stays 1.

Example 3

Input
n = 4, k = 3
Output
20
Why
[1,1,1,1] → [1,2,3,4] → [1,3,6,10] → [1,4,10,20].

Constraints

  • 1 <= n, k <= 1000
  • Return the answer modulo 10^9 + 7.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Simulation (prefix sums)O(n · k)O(n)
Optimal (binomial coefficient)O(k + log p)O(1)

1Simulation (prefix sums)

TimeO(n · k)k passes over n elements.
SpaceO(n)One array of length n.

Keep the array and apply the update k times. Updating left to right in place works because a[i] only needs the new a[i - 1] (which is already the prefix sum up to i - 1) plus its own old value.

  1. Fill a with n ones.
  2. Repeat k times: for i from 1 to n - 1, a[i] = (a[i] + a[i - 1]) mod 10^9 + 7.
  3. Return a[n - 1].
class Solution {
    public int valueAfterKSeconds(int n, int k) {
        final int MOD = 1_000_000_007;
        int[] a = new int[n];
        Arrays.fill(a, 1);
        for (int s = 0; s < k; s++) {
            for (int i = 1; i < n; i++) {
                a[i] = (a[i] + a[i - 1]) % MOD;
            }
        }
        return a[n - 1];
    }
}

2Optimal (binomial coefficient)

TimeO(k + log p)Two products of k terms plus one fast power with about 30 squarings.
SpaceO(1)A few long variables.

The value at index i after s seconds satisfies v(i, s) = v(i - 1, s) + v(i, s - 1) with ones on the borders, which is exactly the rule of Pascal's triangle. So v(n - 1, k) = C(n - 1 + k, k). Compute it as a product of k numerator terms divided by k!, using a modular inverse (Fermat's little theorem, since the modulus is prime).

  1. num = product of (n - 1 + i) for i = 1..k, mod p.
  2. den = k! mod p.
  3. Return num × den^(p - 2) mod p, using fast exponentiation.
class Solution {
    private static final long MOD = 1_000_000_007L;

    public int valueAfterKSeconds(int n, int k) {
        long num = 1, den = 1;
        for (int i = 1; i <= k; i++) {
            num = num * ((n - 1 + i) % MOD) % MOD;
            den = den * i % MOD;
        }
        return (int) (num * power(den, MOD - 2) % MOD);
    }

    private long power(long base, long exp) {
        long result = 1;
        base %= MOD;
        while (exp > 0) {
            if ((exp & 1) == 1) result = result * base % MOD;
            base = base * base % MOD;
            exp >>= 1;
        }
        return result;
    }
}

Edge cases to test

  • n = 1: the answer is always 1
  • k = 1: the answer is n
  • Large n and k: values overflow without taking the modulo at every step

Hints

Hint 1

Each second replaces the array by its prefix sums. Simulate it with one running sum per second.

Hint 2

Look at the table of values: it is Pascal's triangle turned on its side.

Hint 3

The last element after k seconds is the binomial coefficient C(n - 1 + k, k).

FAQ

What is the best time complexity for Find the N-th Value After K Seconds?

Optimal (binomial coefficient) runs in O(k + log p) time and O(1) extra space. Two products of k terms plus one fast power with about 30 squarings.

Which pattern does Find the N-th Value After K Seconds use?

It is a dynamic programming problem that uses the 2d dp pattern. Other problems with the same pattern: Minimum Path Sum, Unique Paths, Unique Paths II.

Is there a brute force solution for Find the N-th Value After K Seconds?

Yes. Simulation (prefix sums) takes O(n · k) time and O(n) space. Keep the array and apply the update k times.

Which edge cases should I test for Find the N-th Value After K Seconds?

n = 1: the answer is always 1; k = 1: the answer is n; Large n and k: values overflow without taking the modulo at every step.