Find the N-th Value After K Seconds

MEDIUM

Description

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 10⁹ + 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

Approaches

Checkout 2 different approaches to solve Find the N-th Value After K Seconds. Click on different approaches to view the approach and algorithm in detail.

Direct Simulation

This approach directly simulates the process described in the problem. We maintain an array representing the state a at each second. We start with an array of n ones. Then, for k seconds, we repeatedly update the array by calculating the prefix sum of the current array.

Algorithm

Define a constant MOD as 10^9 + 7.
Create an integer array a of size n.
Initialize all elements of a to 1.
Loop k times, representing the seconds from 1 to k.
Inside the loop, iterate from i = 1 to n-1:
- Update a[i] by adding the value of the preceding element: a[i] = (a[i] + a[i-1]) % MOD.
After the loops complete, the value at a[n-1] is the final answer.

The most straightforward way to solve this problem is to follow the simulation step-by-step. We begin with an array a of size n, where every element is 1. The problem states that after each second, every element a[i] is updated to be the sum of all preceding elements plus itself. This is equivalent to calculating the prefix sum of the array.

We can perform this simulation for k seconds. In each second, we can update the array in-place. The new value of a[i] is the sum of the old values from a[0] to a[i]. This can be calculated more efficiently as new_a[i] = new_a[i-1] + old_a[i]. Since we iterate from left to right, a[i-1] will already hold its new value for the current second. Thus, the update rule simplifies to a[i] = a[i] + a[i-1] for i > 0.

We repeat this process k times. All additions are performed modulo 10^9 + 7 to prevent integer overflow. After k iterations, a[n-1] will hold the required value.

class Solution {
    public int valueAfterKSeconds(int n, int k) {
        int MOD = 1_000_000_007;
        int[] a = new int[n];
        java.util.Arrays.fill(a, 1);

        // Simulate for k seconds
        for (int second = 0; second < k; second++) {
            // Update the array to its prefix sum
            for (int i = 1; i < n; i++) {
                a[i] = (a[i] + a[i-1]) % MOD;
            }
        }

        return a[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(k * n) - We have a nested loop. The outer loop runs `k` times, and the inner loop for calculating prefix sums runs `n-1` times.Space Complexity: O(n) - We use an array of size `n` to store the values at each second.

Pros and Cons

Pros:

Simple to understand and implement as it directly models the problem statement.
Sufficiently efficient for the given constraints (n, k <= 1000).

Cons:

Less efficient than the mathematical approach, with a quadratic time complexity.
Might be too slow if the constraints on n or k were larger.

Code Solutions

Checking out 3 solutions in different languages for Find the N-th Value After K Seconds. Click on different languages to view the code.

class Solution {
public
  int valueAfterKSeconds(int n, int k) {
    final int mod = (int)1 e9 + 7;
    int[] a = new int[n];
    Arrays.fill(a, 1);
    while (k-- > 0) {
      for (int i = 1; i < n; ++i) {
        a[i] = (a[i] + a[i - 1]) % mod;
      }
    }
    return a[n - 1];
  }
}

Video Solution

Watch the video walkthrough for Find the N-th Value After K Seconds

Patterns:

MathCombinatoricsPrefix Sum

Data Structures:

Array