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

Explanation:

To solve this problem, we can use dynamic programming. We define a 2D array dp where dp[i][j] represents the number of ways to stay at index 0 after i steps when the pointer is at position j. At each step, the pointer can move left, right, or stay at the same position.

We can update the value of dp array based on the previous steps. The number of ways to stay at index 0 after i steps depends on the number of ways to stay at index 0 after i-1 steps. We can consider the cases where we move left, right, or stay in the current step.

Finally, we return the number of ways to stay at index 0 after exactly steps steps, which is dp[steps][0].

Time Complexity:

The time complexity of this solution is O(steps * min(steps, arrLen)).

Space Complexity:

The space complexity of this solution is O(steps * min(steps, arrLen)).

:

class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1000000007;
        int maxPos = Math.min(steps / 2, arrLen - 1);
        int[][] dp = new int[steps + 1][maxPos + 1];
        dp[0][0] = 1;
        
        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxPos; j++) {
                dp[i][j] = dp[i-1][j];
                if (j - 1 >= 0) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j-1]) % mod;
                }
                if (j + 1 <= maxPos) {
                    dp[i][j] = (dp[i][j] + dp[i-1][j+1]) % mod;
                }
            }
        }
        
        return dp[steps][0];
    }
}