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

How it works

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).

Steps

1. Use a single 1D array dp where dp[i] represents ways to reach position i.
2. Initialize dp[0] = 1.
3. 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.
4. Return dp[0].

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.

Things to watch for

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.

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]

class Solution {
public:
    int numWays(int steps, int arrLen) {
        const int MOD = 1e9 + 7;
        arrLen = min(steps, arrLen);
        vector<int> dp(arrLen, 0);
        dp[0] = 1;

        for (int step = 0; step < steps; step++) {
            int prev = 0;
            for (int i = 0; i < arrLen; i++) {
                int 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];
    }
};