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

Problem

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.

Examples

Example 1:

1
2
3
4
5
6
7
8
9

Input:
steps = 3, arrLen = 2
Output:
 4
Explanation: There are 4 differents ways to stay at index 0 after 3 steps.
Right, Left, Stay
Stay, Right, Left
Right, Stay, Left
Stay, Stay, Stay

Example 2:

1
2
3
4
5
6
7

Input:
steps = 2, arrLen = 4
Output:
 2
Explanation: There are 2 differents ways to stay at index 0 after 2 steps
Right, Left
Stay, Stay

Example 3:

1
2
3
4

Input:
steps = 4, arrLen = 2
Output:
 8

Solution

Method 1 – Dynamic Programming

Intuition

Use dynamic programming to count the number of ways to reach each position after each step, ensuring the pointer stays within bounds.

Approach

  1. Let dp[s][i] be the number of ways to be at position i after s steps.
  2. For each step, update dp for each position by considering moves from left, right, and staying.
  3. Only consider positions up to min(arrLen, steps+1) since you can’t move further than the number of steps.
  4. The answer is dp[steps][0].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
    int numWays(int steps, int arrLen) {
        int MOD = 1e9+7, maxPos = min(arrLen, steps+1);
        vector<vector<int>> dp(steps+1, vector<int>(maxPos));
        dp[0][0] = 1;
        for (int s = 1; s <= steps; ++s) {
            for (int i = 0; i < maxPos; ++i) {
                dp[s][i] = dp[s-1][i];
                if (i > 0) dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % MOD;
                if (i+1 < maxPos) dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % MOD;
            }
        }
        return dp[steps][0];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

func numWays(steps int, arrLen int) int {
    mod := int(1e9+7)
    maxPos := min(arrLen, steps+1)
    dp := make([][]int, steps+1)
    for i := range dp {
        dp[i] = make([]int, maxPos)
    }
    dp[0][0] = 1
    for s := 1; s <= steps; s++ {
        for i := 0; i < maxPos; i++ {
            dp[s][i] = dp[s-1][i]
            if i > 0 { dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % mod }
            if i+1 < maxPos { dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % mod }
        }
    }
    return dp[steps][0]
}
func min(a, b int) int { if a < b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public int numWays(int steps, int arrLen) {
        int MOD = 1_000_000_007, maxPos = Math.min(arrLen, steps+1);
        int[][] dp = new int[steps+1][maxPos];
        dp[0][0] = 1;
        for (int s = 1; s <= steps; ++s) {
            for (int i = 0; i < maxPos; ++i) {
                dp[s][i] = dp[s-1][i];
                if (i > 0) dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % MOD;
                if (i+1 < maxPos) dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % MOD;
            }
        }
        return dp[steps][0];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun numWays(steps: Int, arrLen: Int): Int {
        val MOD = 1_000_000_007
        val maxPos = minOf(arrLen, steps+1)
        val dp = Array(steps+1) { IntArray(maxPos) }
        dp[0][0] = 1
        for (s in 1..steps) {
            for (i in 0 until maxPos) {
                dp[s][i] = dp[s-1][i]
                if (i > 0) dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % MOD
                if (i+1 < maxPos) dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % MOD
            }
        }
        return dp[steps][0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        MOD = 10**9+7
        maxPos = min(arrLen, steps+1)
        dp = [[0]*maxPos for _ in range(steps+1)]
        dp[0][0] = 1
        for s in range(1, steps+1):
            for i in range(maxPos):
                dp[s][i] = dp[s-1][i]
                if i > 0:
                    dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % MOD
                if i+1 < maxPos:
                    dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % MOD
        return dp[steps][0]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

impl Solution {
    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
        let mod_val = 1_000_000_007;
        let max_pos = arr_len.min(steps+1) as usize;
        let mut dp = vec![vec![0; max_pos]; (steps+1) as usize];
        dp[0][0] = 1;
        for s in 1..=steps as usize {
            for i in 0..max_pos {
                dp[s][i] = dp[s-1][i];
                if i > 0 {
                    dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % mod_val;
                }
                if i+1 < max_pos {
                    dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % mod_val;
                }
            }
        }
        dp[steps as usize][0]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    numWays(steps: number, arrLen: number): number {
        const MOD = 1e9+7;
        const maxPos = Math.min(arrLen, steps+1);
        const dp: number[][] = Array.from({length: steps+1}, () => Array(maxPos).fill(0));
        dp[0][0] = 1;
        for (let s = 1; s <= steps; ++s) {
            for (let i = 0; i < maxPos; ++i) {
                dp[s][i] = dp[s-1][i];
                if (i > 0) dp[s][i] = (dp[s][i] + dp[s-1][i-1]) % MOD;
                if (i+1 < maxPos) dp[s][i] = (dp[s][i] + dp[s-1][i+1]) % MOD;
            }
        }
        return dp[steps][0];
    }
}

Complexity

  • ⏰ Time complexity: O(steps * arrLen)
    • For each step, we update up to arrLen positions, resulting in O(steps * arrLen) operations.
  • 🧺 Space complexity: O(steps * arrLen)
    • We use a DP table of size (steps+1) x min(arrLen, steps+1) to store the number of ways for each step and position.