1269. Number of Ways to Stay in the Same Place After Some Steps - Explanation

1. Dynamic Programming (Top-Down)

Intuition

We need to count how many ways we can return to index 0 after exactly steps moves, where each move can go left, right, or stay in place. This is a classic decision tree problem where at each step we have three choices.

The key observation is that we can never move further than steps positions to the right, since we would need at least that many steps just to return. This lets us bound our search space to min(steps, arrLen) positions.

We use memoization to avoid recomputing the same subproblems. The state is defined by the current position i and remaining steps.

Algorithm

Limit the effective array length to min(steps, arrLen) since we cannot move further than steps positions.
Define a recursive function dfs(i, steps) that returns the number of ways to reach index 0 from position i with steps moves remaining.
Base case: If steps == 0, return 1 if we are at index 0, otherwise return 0.
For each state, try all three options (stay, move left if i > 0, move right if i < arrLen - 1) and sum the results.
Cache results to avoid redundant computation.
Return dfs(0, steps) as the answer.

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(arrLen, steps)
        dp = {}

        def dfs(i, steps):
            if steps == 0:
                return i == 0
            if (i, steps) in dp:
                return dp[(i, steps)]

            res = dfs(i, steps - 1)
            if i > 0:
                res = (res + dfs(i - 1, steps - 1)) % mod
            if i < arrLen - 1:
                res = (res + dfs(i + 1, steps - 1)) % mod

            dp[(i, steps)] = res
            return res

        return dfs(0, steps)

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(n * min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

2. Dynamic Programming (Bottom-Up)

Intuition

Instead of thinking recursively from the end state backward, we can build up the solution iteratively. We start from the base case (0 steps taken, standing at index 0) and compute how many ways there are to be at each position after 1 step, then 2 steps, and so on.

At each step, the number of ways to reach position i is the sum of ways to reach i from i-1 (moving right), from i (staying), and from i+1 (moving left) in the previous step.

Algorithm

Create a 2D DP table where dp[step][i] represents the number of ways to be at position i after step moves.
Initialize dp[0][0] = 1 since we start at index 0 with 0 steps taken.
For each step from 1 to steps:
- For each position i from 0 to arrLen - 1:
  - Add ways from staying in place: dp[step-1][i]
  - Add ways from moving right (if i > 0): dp[step-1][i-1]
  - Add ways from moving left (if i < arrLen - 1): dp[step-1][i+1]
Return dp[steps][0].

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(arrLen, steps)
        dp = [[0] * (arrLen + 1) for _ in range(steps + 1)]
        dp[0][0] = 1

        for step in range(1, steps + 1):
            for i in range(arrLen):
                res = dp[step - 1][i]
                if i > 0:
                    res = (res + dp[step - 1][i - 1]) % mod
                if i < arrLen - 1:
                    res = (res + dp[step - 1][i + 1]) % mod
                dp[step][i] = res

        return dp[steps][0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(n * min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

3. Dynamic Programming (Space Optimized)

Intuition

Looking at the bottom-up solution, we notice that computing the values for step k only requires values from step k-1. We do not need the entire history of all steps.

This means we can reduce space from O(steps * positions) to O(positions) by keeping only two arrays: one for the current step and one for the previous step.

Algorithm

Use a 1D array dp where dp[i] represents the number of ways to be at position i after the current number of steps.
Initialize dp[0] = 1 for the starting position.
For each step:
- Create a new array next_dp to store results for this step.
- For each position i, compute next_dp[i] by summing contributions from positions i-1, i, and i+1 in dp.
- Replace dp with next_dp.
Return dp[0] after all steps.

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(steps, arrLen)
        dp = [0] * arrLen
        dp[0] = 1

        for _ in range(steps):
            next_dp = [0] * arrLen
            for i in range(arrLen):
                next_dp[i] = dp[i]
                if i > 0:
                    next_dp[i] = (next_dp[i] + dp[i - 1]) % mod
                if i < arrLen - 1:
                    next_dp[i] = (next_dp[i] + dp[i + 1]) % mod
            dp = next_dp

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

4. Dynamic Programming (Optimal)

Intuition

We can push the space optimization even further. Instead of using two separate arrays, we can update the DP array in place if we are careful about the order of updates.

The trick is to process positions from left to right while keeping track of the previous value before it gets overwritten. This way, when we update dp[i], we still have access to the old dp[i-1] (saved in a temporary variable) and the old dp[i+1] (not yet updated).

Algorithm

Use a single 1D array dp where dp[i] represents ways to reach position i.
Initialize dp[0] = 1.
For each step:
- Track prev to store the old value of dp[i-1] before it was updated.
- For each position i from 0 to arrLen - 1:
  - Save the current dp[i] as cur before modifying it.
  - Add prev (contribution from the left) if i > 0.
  - Add dp[i+1] (contribution from the right) if i < arrLen - 1.
  - Update prev = cur for the next iteration.
Return dp[0].

class Solution:
    def numWays(self, steps: int, arrLen: int) -> int:
        mod = 10**9 + 7
        arrLen = min(steps, arrLen)
        dp = [0] * arrLen
        dp[0] = 1

        for _ in range(steps):
            prev = 0
            for i in range(arrLen):
                cur = dp[i]
                if i > 0:
                    dp[i] = (dp[i] + prev) % mod
                if i < arrLen - 1:
                    dp[i] = (dp[i] + dp[i + 1]) % mod
                prev = cur

        return dp[0]

Time & Space Complexity

Time complexity: $O(n * min(n, m))$
Space complexity: $O(min(n, m))$

Where $n$ is the number of steps and $m$ is the size of the array.

Common Pitfalls

Not Bounding the Maximum Reachable Position

Without optimization, the DP table would be O(steps * arrLen) which can be prohibitively large when arrLen is huge but steps is small. The key insight is that you can never move more than steps positions to the right (since you need steps to return). Always limit the effective array length to min(steps, arrLen) to avoid TLE or memory issues.

Incorrect Boundary Checks for Movement

When at position i, moving left requires i > 0 and moving right requires i < arrLen - 1. A common mistake is using i < arrLen for the right boundary (allowing out-of-bounds movement) or forgetting the left boundary check entirely. These off-by-one errors cause incorrect results or runtime errors.

Mixing Up the DP Transition Direction

In bottom-up DP, you need to carefully track whether dp[step][i] represents the number of ways to reach position i after step moves (forward direction) or the number of ways to return to position 0 from position i with step moves remaining (backward direction). Mixing these up leads to incorrect recurrence relations and wrong answers.