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

Runtime      6 ms
Beats       96.34%

Memory      39.2 MB
Beats       96.34%



public class Solution {
    public int numWays(int steps, int arrLen) {
        int mod = 1_000_000_007;
        int maxColumn = Math.min(arrLen, steps / 2 + 1);
        int[] curr = new int[maxColumn + 1];
        int[] prev = new int[maxColumn + 1];
        prev[0] = 1;

        for (int i = 1; i <= steps; i++) {
            for (int j = 0; j <= maxColumn; j++) {
                curr[j] = prev[j];
                if (j - 1 >= 0) {
                    curr[j] = (curr[j] + prev[j - 1]) % mod;
                }
                if (j + 1 < maxColumn) {
                    curr[j] = (curr[j] + prev[j + 1]) % mod;
                }
            }
            System.arraycopy(curr, 0, prev, 0, maxColumn + 1);
        }
        return prev[0];
    }
}