Out of Boundary Paths

Medium · 1-D Dynamic Programming · Explanation and code example

Dynamic Programming (Space Optimized)

How it works

Since each move layer only depends on the previous move layer, we do not need the full 3D array. We can use two 2D arrays: one for the current move count and one for the previous. After processing each move, we swap them.

This reduces space from O(m _ n _ maxMove) to O(m * n).

Steps

  1. Create two 2D arrays: dp for the previous move count and tmp for the current.
  2. For each move from 1 to maxMove:
    • Reset tmp to zeros.
    • For each cell, add 1 for each out-of-bound neighbor, or add dp[neighbor] for valid neighbors.
    • Swap dp and tmp.
  3. Return dp[startRow][startColumn].

Complexity

  • Time complexity: O(m * n * N)
  • Space complexity: O(m * n)

Where m is the number of rows, n is the number of columns, and N is the maximum number of allowed moves.

Things to watch for

Forgetting to Apply Modulo at Each Step

The number of paths can grow extremely large, causing integer overflow. A common mistake is only applying the modulo operation at the end. You must apply % (10^9 + 7) after each addition to prevent overflow, especially when summing results from multiple recursive calls or DP transitions.

Incorrect Base Case for Out-of-Bounds

Some implementations check if moves are zero before checking if the position is out of bounds. The correct order is to first check if we are outside the grid (return 1 for a valid exit path), then check if moves are exhausted (return 0). Reversing this order means we would never count paths that step outside on their last move.

Using Wrong Memoization Key

When using memoization, the cache key must include all three state variables: row, column, and remaining moves. Forgetting to include the move count in the key leads to incorrect caching where different move states overwrite each other, producing wrong answers.

Python code example

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * n for _ in range(m)]

        for moves in range(1, maxMove + 1):
            tmp = [[0] * n for _ in range(m)]
            for r in range(m):
                for c in range(n):
                    if r + 1 == m:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r + 1][c]) % MOD
                    if r - 1 < 0:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r - 1][c]) % MOD
                    if c + 1 == n:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r][c + 1]) % MOD
                    if c - 1 < 0:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r][c - 1]) % MOD
            dp = tmp

        return dp[startRow][startColumn]

C++ code example

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        const int MOD = 1'000'000'007;
        vector<vector<int>> dp(m, vector<int>(n, 0));

        for (int moves = 1; moves <= maxMove; moves++) {
            vector<vector<int>> tmp(m, vector<int>(n, 0));
            for (int r = 0; r < m; r++) {
                for (int c = 0; c < n; c++) {
                    if (r + 1 == m) {
                        tmp[r][c] = (tmp[r][c] + 1) % MOD;
                    } else {
                        tmp[r][c] = (tmp[r][c] + dp[r + 1][c]) % MOD;
                    }
                    if (r - 1 < 0) {
                        tmp[r][c] = (tmp[r][c] + 1) % MOD;
                    } else {
                        tmp[r][c] = (tmp[r][c] + dp[r - 1][c]) % MOD;
                    }
                    if (c + 1 == n) {
                        tmp[r][c] = (tmp[r][c] + 1) % MOD;
                    } else {
                        tmp[r][c] = (tmp[r][c] + dp[r][c + 1]) % MOD;
                    }
                    if (c - 1 < 0) {
                        tmp[r][c] = (tmp[r][c] + 1) % MOD;
                    } else {
                        tmp[r][c] = (tmp[r][c] + dp[r][c - 1]) % MOD;
                    }
                }
            }
            dp = tmp;
        }

        return dp[startRow][startColumn];
    }
};
Source and license

Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.

Check the explanation on LeetCode

Your recall check is in progress. Write your attempt before revealing the explanation.

Resume recall check

Browse all problem explanations