Number of Ways to Stay in the Same Place After Some Steps - Problem

Dynamic Programming Hard

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time).

Given two integers steps and arrLen, return the number of ways such that your pointer is still at index 0 after exactly steps steps.

Since the answer may be too large, return it modulo 10^9 + 7.

Input & Output

Example 1 — Basic Case

$ Input: steps = 3, arrLen = 2

› Output: 4

💡 Note: 4 ways to stay at index 0 after 3 steps: Stay→Stay→Stay, Stay→Right→Left, Right→Stay→Left, Right→Left→Stay

Example 2 — Single Position

$ Input: steps = 2, arrLen = 1

› Output: 1

💡 Note: Only one position available, so must stay at index 0. Only way: Stay→Stay

Example 3 — Larger Array

$ Input: steps = 4, arrLen = 3

› Output: 8

💡 Note: Multiple paths possible with more positions and steps available

Constraints

1 ≤ steps ≤ 500
1 ≤ arrLen ≤ 10⁶
The answer is guaranteed to fit in a 32-bit integer

Visualization

Tap to expand

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

This problem requires dynamic programming to count paths efficiently. The key insight is that we can track (position, remaining_steps) states and build solutions bottom-up. The optimal approach uses space-optimized 1D DP with Time: O(steps × arrLen), Space: O(arrLen).

Common Approaches

✓ 2D Dynamic Programming

⏱️ Time: O(steps × arrLen) Space: O(steps × arrLen)

Create a 2D DP table where dp[i][j] represents number of ways to be at position j after exactly i steps. Fill the table iteratively from base case to final answer.

Memoized Recursion

⏱️ Time: O(steps × arrLen) Space: O(steps × arrLen)

Same recursive approach but store results of (position, steps) pairs in a memoization table. When we encounter the same state again, return the cached result instead of recalculating.

Recursive Brute Force

⏱️ Time: O(3^steps) Space: O(steps)

For each step, recursively try all three moves (left, right, stay) and count paths that end at position 0. This explores every possible combination without memoization.

Space-Optimized 1D DP

⏱️ Time: O(steps × arrLen) Space: O(arrLen)

Since we only need the previous step's results to compute the current step, we can use two 1D arrays and alternate between them. This reduces space complexity significantly.

2D Dynamic Programming — Algorithm Steps

Initialize DP table: dp[steps+1][arrLen]
Base case: dp[0][0] = 1 (1 way to be at pos 0 with 0 steps)
Fill table: dp[i][j] = sum of ways from adjacent positions at step i-1
Return dp[steps][0] as final answer

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Set dp[0][0] = 1, all others = 0

Fill Table

Each cell = sum of three previous positions

Answer

Return dp[steps][0]

Code -

solution.c — C

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

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int steps, int arrLen) {
    const int MOD = 1000000007;
    
    // Optimize: we can't go further than steps/2 positions away
    int maxPos = min(arrLen - 1, steps / 2);
    
    // dp[i][j] = ways to be at position j after i steps
    int dp[501][251];  // Assuming reasonable limits
    memset(dp, 0, sizeof(dp));
    dp[0][0] = 1;  // Base case: 1 way to be at pos 0 with 0 steps
    
    for (int i = 1; i <= steps; i++) {
        for (int j = 0; j <= maxPos; j++) {
            // Stay at current position
            dp[i][j] = dp[i-1][j];
            // Come from left (j-1)
            if (j > 0) {
                dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % MOD;
            }
            // Come from right (j+1)
            if (j < maxPos) {
                dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % MOD;
            }
        }
    }
    
    return dp[steps][0];
}

int main() {
    int steps, arrLen;
    scanf("%d", &steps);
    scanf("%d", &arrLen);
    int result = solution(steps, arrLen);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(steps × arrLen)

Double nested loop iterates through steps×arrLen cells, each with constant work

✓ Linear Growth

Space Complexity

O(steps × arrLen)

2D DP table stores steps×arrLen values

✓ Linear Space

28.0K Views

Medium Frequency

~25 min Avg. Time

892 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

Number of Ways to Stay in the Same Place After Some Steps - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler