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

Description

Start at index 0 of an array with arrLen positions. On each of exactly steps turns, move one position left, move one position right, or remain at your current position. Every intermediate position must lie inside the array. Count the distinct sequences of actions that finish at index 0, and return the count modulo 1000000007.

Example 1:

Input: steps = 1
arrLen = 5

Output: 1

Explanation: With only one action, staying at index 0 is the only way to finish there. Moving right would end at index 1, and moving left is outside the array.

Example 2:

Input: steps = 5
arrLen = 1

Output: 1

Explanation: The array has only index 0, so every action must be Stay. The sequence of five Stay actions is the only valid sequence.

Example 3:

Input: steps = 3
arrLen = 3

Output: 4

Explanation: The four sequences are Stay-Stay-Stay, Stay-Right-Left, Right-Stay-Left, and Right-Left-Stay. Reaching index 2 would leave too few actions to return to 0.

Constraints:

1 <= steps <= 500
1 <= arrLen <= 1000000

Topics

Dynamic Programming

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Dynamic Programming - Using memoization (top-down) or tabulation (bottom-up) to solve problems with overlapping subproblems
Recursion - Breaking down problems into smaller cases and identifying base cases
State Space Optimization - Recognizing when to bound the search space (e.g., you cannot move further than steps positions)
Modular Arithmetic - Working with results modulo 10^9 + 7 to handle large numbers

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)

public class Solution {
    private static final int MOD = 1_000_000_007;
    private int[][] dp;

    public int numWays(int steps, int arrLen) {
        int maxPos = Math.min(steps, arrLen);
        dp = new int[maxPos + 1][steps + 1];
        for (int i = 0; i <= maxPos; i++) {
            for (int j = 0; j <= steps; j++) {
                dp[i][j] = -1;
            }
        }
        return dfs(0, steps, maxPos);
    }

    private int dfs(int i, int steps, int maxPos) {
        if (steps == 0) {
            return i == 0 ? 1 : 0;
        }
        if (dp[i][steps] != -1) {
            return dp[i][steps];
        }

        int res = dfs(i, steps - 1, maxPos);
        if (i > 0) {
            res = (res + dfs(i - 1, steps - 1, maxPos)) % MOD;
        }
        if (i < maxPos - 1) {
            res = (res + dfs(i + 1, steps - 1, maxPos)) % MOD;
        }

        dp[i][steps] = res;
        return res;
    }
}

class Solution {
private:
    static const int MOD = 1e9 + 7;
    vector<vector<int>> dp;

    int dfs(int i, int steps, int maxPos) {
        if (steps == 0) {
            return i == 0 ? 1 : 0;
        }
        if (dp[i][steps] != -1) {
            return dp[i][steps];
        }

        int res = dfs(i, steps - 1, maxPos);
        if (i > 0) {
            res = (res + dfs(i - 1, steps - 1, maxPos)) % MOD;
        }
        if (i < maxPos - 1) {
            res = (res + dfs(i + 1, steps - 1, maxPos)) % MOD;
        }

        dp[i][steps] = res;
        return res;
    }

public:
    int numWays(int steps, int arrLen) {
        int maxPos = min(steps, arrLen);
        dp.assign(maxPos + 1, vector<int>(steps + 1, -1));
        return dfs(0, steps, maxPos);
    }
};

class Solution {
    /**
     * @param {number} steps
     * @param {number} arrLen
     * @return {number}
     */
    numWays(steps, arrLen) {
        const MOD = 1e9 + 7;
        const maxPos = Math.min(steps, arrLen);
        const dp = Array.from({ length: maxPos + 1 }, () =>
            Array(steps + 1).fill(-1),
        );

        const dfs = (i, steps) => {
            if (steps === 0) return i === 0 ? 1 : 0;
            if (dp[i][steps] !== -1) return dp[i][steps];

            let res = dfs(i, steps - 1);
            if (i > 0) res = (res + dfs(i - 1, steps - 1)) % MOD;
            if (i < maxPos - 1) res = (res + dfs(i + 1, steps - 1)) % MOD;

            dp[i][steps] = res;
            return res;
        };

        return dfs(0, steps);
    }
}

public class Solution {
    private const int MOD = 1_000_000_007;
    private int[,] dp;

    public int NumWays(int steps, int arrLen) {
        int maxPos = Math.Min(steps, arrLen);
        dp = new int[maxPos + 1, steps + 1];
        for (int i = 0; i <= maxPos; i++) {
            for (int j = 0; j <= steps; j++) {
                dp[i, j] = -1;
            }
        }
        return Dfs(0, steps, maxPos);
    }

    private int Dfs(int i, int steps, int maxPos) {
        if (steps == 0) return i == 0 ? 1 : 0;
        if (dp[i, steps] != -1) return dp[i, steps];

        int res = Dfs(i, steps - 1, maxPos);
        if (i > 0) res = (res + Dfs(i - 1, steps - 1, maxPos)) % MOD;
        if (i < maxPos - 1) res = (res + Dfs(i + 1, steps - 1, maxPos)) % MOD;

        dp[i, steps] = res;
        return res;
    }
}

func numWays(steps int, arrLen int) int {
    MOD := int(1e9 + 7)
    maxPos := min(steps, arrLen)
    dp := make([][]int, maxPos+1)
    for i := range dp {
        dp[i] = make([]int, steps+1)
        for j := range dp[i] {
            dp[i][j] = -1
        }
    }

    var dfs func(i, steps int) int
    dfs = func(i, steps int) int {
        if steps == 0 {
            if i == 0 {
                return 1
            }
            return 0
        }
        if dp[i][steps] != -1 {
            return dp[i][steps]
        }

        res := dfs(i, steps-1)
        if i > 0 {
            res = (res + dfs(i-1, steps-1)) % MOD
        }
        if i < maxPos-1 {
            res = (res + dfs(i+1, steps-1)) % MOD
        }

        dp[i][steps] = res
        return res
    }

    return dfs(0, steps)
}

class Solution {
    private val MOD = 1_000_000_007
    private lateinit var dp: Array<IntArray>

    fun numWays(steps: Int, arrLen: Int): Int {
        val maxPos = minOf(steps, arrLen)
        dp = Array(maxPos + 1) { IntArray(steps + 1) { -1 } }
        return dfs(0, steps, maxPos)
    }

    private fun dfs(i: Int, steps: Int, maxPos: Int): Int {
        if (steps == 0) return if (i == 0) 1 else 0
        if (dp[i][steps] != -1) return dp[i][steps]

        var res = dfs(i, steps - 1, maxPos)
        if (i > 0) res = (res + dfs(i - 1, steps - 1, maxPos)) % MOD
        if (i < maxPos - 1) res = (res + dfs(i + 1, steps - 1, maxPos)) % MOD

        dp[i][steps] = res
        return res
    }
}

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let MOD = 1_000_000_007
        let maxPos = min(steps, arrLen)
        var dp = [[Int]](repeating: [Int](repeating: -1, count: steps + 1), count: maxPos + 1)

        func dfs(_ i: Int, _ steps: Int) -> Int {
            if steps == 0 { return i == 0 ? 1 : 0 }
            if dp[i][steps] != -1 { return dp[i][steps] }

            var res = dfs(i, steps - 1)
            if i > 0 { res = (res + dfs(i - 1, steps - 1)) % MOD }
            if i < maxPos - 1 { res = (res + dfs(i + 1, steps - 1)) % MOD }

            dp[i][steps] = res
            return res
        }

        return dfs(0, steps)
    }
}

impl Solution {
    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let max_pos = steps.min(arr_len) as usize;
        let steps = steps as usize;
        let mut dp = vec![vec![-1i32; steps + 1]; max_pos + 1];

        fn dfs(i: usize, steps: usize, max_pos: usize, dp: &mut Vec<Vec<i32>>) -> i32 {
            if steps == 0 {
                return if i == 0 { 1 } else { 0 };
            }
            if dp[i][steps] != -1 { return dp[i][steps]; }

            let mut res = dfs(i, steps - 1, max_pos, dp);
            if i > 0 {
                res = (res + dfs(i - 1, steps - 1, max_pos, dp)) % MOD;
            }
            if i < max_pos - 1 {
                res = (res + dfs(i + 1, steps - 1, max_pos, dp)) % MOD;
            }

            dp[i][steps] = res;
            res
        }

        dfs(0, steps, max_pos, &mut dp)
    }
}

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]

public class Solution {
    public int numWays(int steps, int arrLen) {
        final int MOD = 1_000_000_007;
        arrLen = Math.min(arrLen, steps);
        int[][] dp = new int[steps + 1][arrLen + 1];
        dp[0][0] = 1;

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

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

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

class Solution {
    /**
     * @param {number} steps
     * @param {number} arrLen
     * @return {number}
     */
    numWays(steps, arrLen) {
        const MOD = 1e9 + 7;
        arrLen = Math.min(arrLen, steps);
        const dp = Array.from({ length: steps + 1 }, () =>
            Array(arrLen + 1).fill(0),
        );
        dp[0][0] = 1;

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

public class Solution {
    public int NumWays(int steps, int arrLen) {
        int MOD = 1_000_000_007;
        arrLen = Math.Min(arrLen, steps);
        int[,] dp = new int[steps + 1, arrLen + 1];
        dp[0, 0] = 1;

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

func numWays(steps int, arrLen int) int {
    MOD := int(1e9 + 7)
    if arrLen > steps {
        arrLen = steps
    }
    dp := make([][]int, steps+1)
    for i := range dp {
        dp[i] = make([]int, arrLen+1)
    }
    dp[0][0] = 1

    for step := 1; step <= steps; step++ {
        for i := 0; i < arrLen; i++ {
            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]
}

class Solution {
    fun numWays(steps: Int, arrLen: Int): Int {
        val MOD = 1_000_000_007
        val len = minOf(arrLen, steps)
        val dp = Array(steps + 1) { IntArray(len + 1) }
        dp[0][0] = 1

        for (step in 1..steps) {
            for (i in 0 until len) {
                var res = dp[step - 1][i]
                if (i > 0) {
                    res = (res + dp[step - 1][i - 1]) % MOD
                }
                if (i < len - 1) {
                    res = (res + dp[step - 1][i + 1]) % MOD
                }
                dp[step][i] = res
            }
        }

        return dp[steps][0]
    }
}

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let MOD = 1_000_000_007
        let len = min(arrLen, steps)
        var dp = [[Int]](repeating: [Int](repeating: 0, count: len + 1), count: steps + 1)
        dp[0][0] = 1

        for step in 1...steps {
            for i in 0..<len {
                var res = dp[step - 1][i]
                if i > 0 {
                    res = (res + dp[step - 1][i - 1]) % MOD
                }
                if i < len - 1 {
                    res = (res + dp[step - 1][i + 1]) % MOD
                }
                dp[step][i] = res
            }
        }

        return dp[steps][0]
    }
}

impl Solution {
    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let arr_len = (arr_len as usize).min(steps as usize);
        let steps = steps as usize;
        let mut dp = vec![vec![0i32; arr_len + 1]; steps + 1];
        dp[0][0] = 1;

        for step in 1..=steps {
            for i in 0..arr_len {
                let mut res = dp[step - 1][i];
                if i > 0 {
                    res = (res + dp[step - 1][i - 1]) % MOD;
                }
                if i < arr_len - 1 {
                    res = (res + dp[step - 1][i + 1]) % MOD;
                }
                dp[step][i] = res;
            }
        }

        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]

public class Solution {
    public int numWays(int steps, int arrLen) {
        final int MOD = 1_000_000_007;
        arrLen = Math.min(steps, arrLen);
        int[] dp = new int[arrLen];
        dp[0] = 1;

        for (int step = 0; step < steps; step++) {
            int[] nextDp = new int[arrLen];
            for (int i = 0; i < arrLen; i++) {
                nextDp[i] = dp[i];
                if (i > 0) {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD;
                }
                if (i < arrLen - 1) {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD;
                }
            }
            dp = nextDp;
        }

        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++) {
            vector<int> nextDp(arrLen, 0);
            for (int i = 0; i < arrLen; i++) {
                nextDp[i] = dp[i];
                if (i > 0) {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD;
                }
                if (i < arrLen - 1) {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD;
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
};

class Solution {
    /**
     * @param {number} steps
     * @param {number} arrLen
     * @return {number}
     */
    numWays(steps, arrLen) {
        const MOD = 1e9 + 7;
        arrLen = Math.min(steps, arrLen);
        let dp = new Array(arrLen).fill(0);
        dp[0] = 1;

        for (let step = 0; step < steps; step++) {
            const nextDp = new Array(arrLen).fill(0);
            for (let i = 0; i < arrLen; i++) {
                nextDp[i] = dp[i];
                if (i > 0) {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD;
                }
                if (i < arrLen - 1) {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD;
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
}

public class Solution {
    public int NumWays(int steps, int arrLen) {
        int MOD = 1_000_000_007;
        arrLen = Math.Min(steps, arrLen);
        int[] dp = new int[arrLen];
        dp[0] = 1;

        for (int step = 0; step < steps; step++) {
            int[] nextDp = new int[arrLen];
            for (int i = 0; i < arrLen; i++) {
                nextDp[i] = dp[i];
                if (i > 0) {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD;
                }
                if (i < arrLen - 1) {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD;
                }
            }
            dp = nextDp;
        }

        return dp[0];
    }
}

func numWays(steps int, arrLen int) int {
    MOD := int(1e9 + 7)
    if arrLen > steps {
        arrLen = steps
    }
    dp := make([]int, arrLen)
    dp[0] = 1

    for step := 0; step < steps; step++ {
        nextDp := make([]int, arrLen)
        for i := 0; i < arrLen; i++ {
            nextDp[i] = dp[i]
            if i > 0 {
                nextDp[i] = (nextDp[i] + dp[i-1]) % MOD
            }
            if i < arrLen-1 {
                nextDp[i] = (nextDp[i] + dp[i+1]) % MOD
            }
        }
        dp = nextDp
    }

    return dp[0]
}

class Solution {
    fun numWays(steps: Int, arrLen: Int): Int {
        val MOD = 1_000_000_007
        val len = minOf(steps, arrLen)
        var dp = IntArray(len)
        dp[0] = 1

        repeat(steps) {
            val nextDp = IntArray(len)
            for (i in 0 until len) {
                nextDp[i] = dp[i]
                if (i > 0) {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD
                }
                if (i < len - 1) {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD
                }
            }
            dp = nextDp
        }

        return dp[0]
    }
}

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let MOD = 1_000_000_007
        let len = min(steps, arrLen)
        var dp = [Int](repeating: 0, count: len)
        dp[0] = 1

        for _ in 0..<steps {
            var nextDp = [Int](repeating: 0, count: len)
            for i in 0..<len {
                nextDp[i] = dp[i]
                if i > 0 {
                    nextDp[i] = (nextDp[i] + dp[i - 1]) % MOD
                }
                if i < len - 1 {
                    nextDp[i] = (nextDp[i] + dp[i + 1]) % MOD
                }
            }
            dp = nextDp
        }

        return dp[0]
    }
}

impl Solution {
    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let len = (steps as usize).min(arr_len as usize);
        let steps = steps as usize;
        let mut dp = vec![0i32; len];
        dp[0] = 1;

        for _ in 0..steps {
            let mut next_dp = vec![0i32; len];
            for i in 0..len {
                next_dp[i] = dp[i];
                if i > 0 {
                    next_dp[i] = (next_dp[i] + dp[i - 1]) % MOD;
                }
                if i < len - 1 {
                    next_dp[i] = (next_dp[i] + dp[i + 1]) % MOD;
                }
            }
            dp = next_dp;
        }

        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]

public class Solution {
    public int numWays(int steps, int arrLen) {
        final int MOD = 1_000_000_007;
        arrLen = Math.min(steps, arrLen);
        int[] dp = new int[arrLen];
        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];
    }
}

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];
    }
};

class Solution {
    /**
     * @param {number} steps
     * @param {number} arrLen
     * @return {number}
     */
    numWays(steps, arrLen) {
        const MOD = 1e9 + 7;
        arrLen = Math.min(steps, arrLen);
        const dp = new Array(arrLen).fill(0);
        dp[0] = 1;

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

public class Solution {
    public int NumWays(int steps, int arrLen) {
        int MOD = 1_000_000_007;
        arrLen = Math.Min(steps, arrLen);
        int[] dp = new int[arrLen];
        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];
    }
}

func numWays(steps int, arrLen int) int {
    MOD := int(1e9 + 7)
    if arrLen > steps {
        arrLen = steps
    }
    dp := make([]int, arrLen)
    dp[0] = 1

    for step := 0; step < steps; step++ {
        prev := 0
        for i := 0; i < arrLen; i++ {
            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 {
    fun numWays(steps: Int, arrLen: Int): Int {
        val MOD = 1_000_000_007
        val len = minOf(steps, arrLen)
        val dp = IntArray(len)
        dp[0] = 1

        repeat(steps) {
            var prev = 0
            for (i in 0 until len) {
                val cur = dp[i]
                if (i > 0) {
                    dp[i] = (dp[i] + prev) % MOD
                }
                if (i < len - 1) {
                    dp[i] = (dp[i] + dp[i + 1]) % MOD
                }
                prev = cur
            }
        }

        return dp[0]
    }
}

class Solution {
    func numWays(_ steps: Int, _ arrLen: Int) -> Int {
        let MOD = 1_000_000_007
        let len = min(steps, arrLen)
        var dp = [Int](repeating: 0, count: len)
        dp[0] = 1

        for _ in 0..<steps {
            var prev = 0
            for i in 0..<len {
                let cur = dp[i]
                if i > 0 {
                    dp[i] = (dp[i] + prev) % MOD
                }
                if i < len - 1 {
                    dp[i] = (dp[i] + dp[i + 1]) % MOD
                }
                prev = cur
            }
        }

        return dp[0]
    }
}

impl Solution {
    pub fn num_ways(steps: i32, arr_len: i32) -> i32 {
        const MOD: i32 = 1_000_000_007;
        let len = (steps as usize).min(arr_len as usize);
        let steps = steps as usize;
        let mut dp = vec![0i32; len];
        dp[0] = 1;

        for _ in 0..steps {
            let mut prev = 0i32;
            for i in 0..len {
                let cur = dp[i];
                if i > 0 {
                    dp[i] = (dp[i] + prev) % MOD;
                }
                if i < len - 1 {
                    dp[i] = (dp[i] + dp[i + 1]) % MOD;
                }
                prev = cur;
            }
        }

        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.