Find the N-th Value After K Seconds - Practice Coding Problems

Find the N-th Value After K Seconds - Problem

Array Math Simulation Combinatorics Prefix Sum Medium

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^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: n = 4, k = 2

› Output: 10

💡 Note: Initial: [1,1,1,1]. After 1s: [1,2,3,4]. After 2s: [1,3,6,10]. Return a[3] = 10.

Example 2 — Single Element

$ Input: n = 1, k = 3

› Output: 1

💡 Note: Array has only one element [1], which never changes regardless of k.

Example 3 — No Time Elapsed

$ Input: n = 3, k = 0

› Output: 1

💡 Note: No seconds pass, so array remains [1,1,1]. Return a[2] = 1.

Constraints

1 ≤ n ≤ 1000
0 ≤ k ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array of n ones, simulate for k seconds

Process

Each second: element = sum of all left elements + itself

Output

Return last element after k seconds

Key Takeaway

🎯 Key Insight: The pattern follows Pascal's triangle - use mathematical formula for optimal O(n) solution

Asked in

G Google 25 M Microsoft 20 a Amazon 15

The key insight is recognizing this follows Pascal's triangle pattern. Each element after k seconds equals the binomial coefficient C(k+i, i). Best approach uses the mathematical formula to directly calculate C(k+n-1, n-1). Time: O(n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Simulation	O(n × k)	O(n)	Simulate each second by calculating prefix sums for all positions
Optimized Prefix Sum	O(n × k)	O(1)	Use in-place prefix sum calculation to avoid extra array allocation
Mathematical Formula	O(n)	O(1)	Recognize the pattern follows binomial coefficients from Pascal's triangle

Brute Force Simulation — Algorithm Steps

Initialize array with all 1s
For each second, calculate new values using prefix sums
Return the last element after k seconds

Visualization

Tap to expand

Step-by-Step Walkthrough

Initial State

Array starts with all 1s

Each Second

Calculate prefix sums for new array

Result

Return last element after k seconds

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int n, int k) {
    const int MOD = 1000000007;
    long long* a = (long long*)malloc(n * sizeof(long long));
    long long* nextA = (long long*)malloc(n * sizeof(long long));
    
    for (int i = 0; i < n; i++) {
        a[i] = 1;
    }
    
    for (int second = 0; second < k; second++) {
        long long prefixSum = 0;
        for (int i = 0; i < n; i++) {
            prefixSum = (prefixSum + a[i]) % MOD;
            nextA[i] = prefixSum;
        }
        long long* temp = a;
        a = nextA;
        nextA = temp;
    }
    
    int result = (int)a[n - 1];
    free(a);
    free(nextA);
    return result;
}

int main() {
    int n, k;
    scanf("%d", &n);
    scanf("%d", &k);
    printf("%d\n", solution(n, k));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For each of k seconds, we iterate through n elements to calculate prefix sums

✓ Linear Growth

Space Complexity

O(n)

Need extra array to store the next state during each simulation step

⚡ Linearithmic Space

21.3K Views

Medium Frequency

~15 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Simulation — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler