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

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 (if not at leftmost boundary)
Move 1 position to the right (if not at rightmost boundary)
Stay in the same place

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

Note: The pointer should not be placed outside the array at any time.

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

Input & Output

Example 1 — Basic Case

$ Input: steps = 3, arrLen = 2

› Output: 4

💡 Note: 4 ways to return to position 0: Stay-Stay-Stay, Stay-Right-Left, Right-Left-Stay, Right-Left-Left (invalid), Left-Right-Stay (invalid). Valid ways: Stay-Stay-Stay, Stay-Right-Left, Right-Left-Stay, Right-Stay-Left = 4 ways

Example 2 — Single Position

$ Input: steps = 2, arrLen = 1

› Output: 1

💡 Note: Only one position available, so the only way is Stay-Stay = 1 way

Example 3 — More Steps

$ Input: steps = 4, arrLen = 3

› Output: 8

💡 Note: With 4 steps in a 3-position array, there are 8 different ways to end up back at position 0

Constraints

1 ≤ steps ≤ 500
1 ≤ arrLen ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array length and number of steps to take

Process

Count all valid move sequences

Output

Number of ways to return to start position

Key Takeaway

🎯 Key Insight: Use dynamic programming to count paths by building up from smaller subproblems

Asked in

G Google 45 a Amazon 35 M Microsoft 25

The key insight is that this is a path counting problem where we need to track ways to reach each position after each step. The optimal approach uses space-optimized dynamic programming with time complexity O(steps × min(steps, arrLen)) and space O(min(steps, arrLen)).

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(steps × min(steps, arrLen))	O(steps × min(steps, arrLen))	Cache recursive results to avoid repeated calculations
Recursive Brute Force	O(3^n)	O(n)	Try all possible move sequences recursively
Space Optimized DP	O(steps × min(steps, arrLen))	O(min(steps, arrLen))	Optimize space by using only two 1D arrays
2D Dynamic Programming	O(steps × min(steps, arrLen))	O(steps × min(steps, arrLen))	Build bottom-up solution using 2D DP table

Memoized Recursion — Algorithm Steps

Use recursion with memoization table
Cache results for each (position, remaining_steps) state
Return cached result if already computed

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate result and store in memo table

Cache Hit

Same state found - return cached result

Efficiency

Each state calculated only once

Code -

solution.c — C

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

#define MOD 1000000007
#define MAXN 505

int memo[MAXN][MAXN];
int visited[MAXN][MAXN];

int dfs(int pos, int remainingSteps, int arrLen) {
    if (remainingSteps == 0) {
        return pos == 0 ? 1 : 0;
    }
    
    if (visited[pos][remainingSteps]) {
        return memo[pos][remainingSteps];
    }
    
    long long ways = 0;
    // Stay in same position
    ways += dfs(pos, remainingSteps - 1, arrLen);
    
    // Move left
    if (pos > 0) {
        ways += dfs(pos - 1, remainingSteps - 1, arrLen);
    }
    
    // Move right
    if (pos < arrLen - 1) {
        ways += dfs(pos + 1, remainingSteps - 1, arrLen);
    }
    
    memo[pos][remainingSteps] = ways % MOD;
    visited[pos][remainingSteps] = 1;
    return memo[pos][remainingSteps];
}

int solution(int steps, int arrLen) {
    memset(visited, 0, sizeof(visited));
    return dfs(0, steps, arrLen);
}

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 × min(steps, arrLen))

We calculate each unique (position, steps) state exactly once

✓ Linear Growth

Space Complexity

O(steps × min(steps, arrLen))

Memoization table stores results for all states plus recursion stack

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~25 min Avg. Time

890 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

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler