# Out of Boundary Paths
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/out-of-boundary-paths)
Canonical: https://scaleengineer.com/dsa/problems/out-of-boundary-paths
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Companies:** [Baidu](https://scaleengineer.com/companies/baidu)
---
## Problem
There is an `m x n` grid with a ball. The ball is initially at the position `[startRow, startColumn]`. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the grid crossing the grid boundary). You can apply **at most** `maxMove` moves to the ball.

Given the five integers `m`, `n`, `maxMove`, `startRow`, `startColumn`, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/out-of-boundary-paths/image0.png) 

**Input:** m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
**Output:** 6

**Example 2:**

![](https://assets.glich.co/dsa/out-of-boundary-paths/image1.png) 

**Input:** m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
**Output:** 12

**Constraints:**

* `1 <= m, n <= 50`
* `0 <= maxMove <= 50`
* `0 <= startRow < m`
* `0 <= startColumn < n`

# Approaches
## Brute-Force Recursion
This approach uses a simple recursive function to explore all possible paths from the starting cell. For each cell and remaining number of moves, it recursively calls itself for all four adjacent cells. The base cases handle situations where the ball goes out of bounds (a valid path) or runs out of moves while inside the grid (an invalid path).
**Time:** O(4^maxMove). For each move, we branch into 4 possibilities. The depth of the recursion is `maxMove`. · **Space:** O(maxMove). This is for the recursion stack depth.
**Pros:** Simple to understand and implement.; Directly translates the problem's definition into code.
**Cons:** Extremely inefficient due to a massive number of overlapping subproblems.; Will result in a "Time Limit Exceeded" (TLE) error for the given constraints.
### Explanation
We define a recursive function, say `findPaths(row, col, movesLeft)`.

- **Base Cases:**
    - If the current position `(row, col)` is outside the grid boundaries (`row < 0`, `row >= m`, `col < 0`, or `col >= n`), it means we have found one path out of the grid. We return 1.
    - If `movesLeft` is 0, we have no more moves left. Since we are still within the grid, this path does not lead out. We return 0.
- **Recursive Step:**
    - From the current cell `(row, col)`, we can move in four directions: up, down, left, and right.
    - The total number of paths is the sum of the paths from each of these four moves. We make a recursive call for each direction with `movesLeft - 1`.
    - `paths = findPaths(row-1, col, movesLeft-1) + findPaths(row+1, col, movesLeft-1) + findPaths(row, col-1, movesLeft-1) + findPaths(row, col+1, movesLeft-1)`.
    - We must apply the modulo `10^9 + 7` to the sum to prevent overflow.
- The initial call to the function will be `findPaths(startRow, startColumn, maxMove)`.
- This method explores every possible path of length up to `maxMove`, leading to a large number of redundant calculations for the same state `(row, col, movesLeft)`.
```java
class Solution {
    int MOD = 1000000007;
    int m, n;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        this.m = m;
        this.n = n;
        return solve(startRow, startColumn, maxMove);
    }

    private int solve(int r, int c, int moves) {
        // Base case: moved out of bounds
        if (r < 0 || r >= m || c < 0 || c >= n) {
            return 1;
        }
        // Base case: no moves left
        if (moves == 0) {
            return 0;
        }

        long paths = 0;
        // Move up
        paths = (paths + solve(r - 1, c, moves - 1)) % MOD;
        // Move down
        paths = (paths + solve(r + 1, c, moves - 1)) % MOD;
        // Move left
        paths = (paths + solve(r, c - 1, moves - 1)) % MOD;
        // Move right
        paths = (paths + solve(r, c + 1, moves - 1)) % MOD;

        return (int) paths;
    }
}
```
### Algorithm
- `1. Define a recursive function `solve(r, c, moves)` that returns the number of paths to get out of bounds from `(r, c)` with `moves` left.`
- `2. Base Case 1: If `(r, c)` is out of bounds, return 1.`
- `3. Base Case 2: If `moves` is 0, return 0.`
- `4. Recursive Step: Sum the results of calling `solve` for the four adjacent cells (up, down, left, right) with `moves - 1`.`
- `5. Apply modulo `10^9 + 7` at each addition.`
- `6. The initial call is `solve(startRow, startColumn, maxMove)`.`

## Dynamic Programming with Memoization (Top-Down)
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. A 3D array `memo[row][col][movesLeft]` is used to cache the number of paths from cell `(row, col)` with `movesLeft` moves remaining. This avoids re-computation and drastically reduces the time complexity.
**Time:** O(m * n * maxMove). Each state `(row, col, movesLeft)` is computed only once. The number of states is `m * n * maxMove`. · **Space:** O(m * n * maxMove). This is for the memoization table. The recursion stack depth adds `O(maxMove)`.
**Pros:** Significantly more efficient than brute-force.; Guaranteed to pass within the time limits for the given constraints.; Still maintains a relatively clear, recursive structure.
**Cons:** Uses significant space for the memoization table.; Can lead to a `StackOverflowError` for very deep recursion, although not an issue with the given constraints (`maxMove <= 50`).
### Explanation
The core idea is to recognize that the recursive function `findPaths(row, col, movesLeft)` is called multiple times with the same arguments. We can store the result of each unique call and reuse it when needed.

- We use a 3D array, `memo[m][n][maxMove + 1]`, to store the computed results. Each entry `memo[r][c][k]` will store the number of ways to move out of the grid from cell `(r, c)` with `k` moves.
- We initialize this memoization table with a sentinel value (e.g., -1 or null) to indicate that the state has not been computed yet.
- The recursive function is modified as follows:
    - Before computing the result for `(r, c, moves)`, we first check if `memo[r][c][moves]` has already been computed. If it has, we return the stored value directly.
    - If not, we compute the result as in the brute-force approach.
    - Before returning, we store the computed result in `memo[r][c][moves]` for future use.
```java
class Solution {
    int MOD = 1000000007;
    int m, n;
    Integer[][][] memo;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        this.m = m;
        this.n = n;
        this.memo = new Integer[m][n][maxMove + 1];
        return solve(startRow, startColumn, maxMove);
    }

    private int solve(int r, int c, int moves) {
        // Base case: moved out of bounds
        if (r < 0 || r >= m || c < 0 || c >= n) {
            return 1;
        }
        // Base case: no moves left
        if (moves == 0) {
            return 0;
        }
        // Memoization check
        if (memo[r][c][moves] != null) {
            return memo[r][c][moves];
        }

        long paths = 0;
        paths = (paths + solve(r - 1, c, moves - 1)) % MOD;
        paths = (paths + solve(r + 1, c, moves - 1)) % MOD;
        paths = (paths + solve(r, c - 1, moves - 1)) % MOD;
        paths = (paths + solve(r, c + 1, moves - 1)) % MOD;

        // Store result in memo table
        memo[r][c][moves] = (int) paths;
        return memo[r][c][moves];
    }
}
```
### Algorithm
- `1. Create a 3D memoization table `memo[m][n][maxMove + 1]` and initialize it with a value indicating 'not computed' (e.g., null or -1).`
- `2. Define a recursive function `solve(r, c, moves)`.`
- `3. Base Case 1: If `(r, c)` is out of bounds, return 1.`
- `4. Base Case 2: If `moves` is 0, return 0.`
- `5. Memoization Check: If `memo[r][c][moves]` is already computed, return its value.`
- `6. Recursive Step: Sum the results of calling `solve` for the four adjacent cells with `moves - 1`.`
- `7. Store the result in `memo[r][c][moves]` before returning.`
- `8. The initial call is `solve(startRow, startColumn, maxMove)`.`

## Dynamic Programming with Space Optimization (Bottom-Up)
This is the most efficient approach. It uses an iterative, bottom-up dynamic programming method. Instead of recursion, we build up the solution iteratively. We maintain a 2D DP table, `dp[m][n]`, where `dp[i][j]` stores the number of ways to reach cell `(i, j)`. We iterate from 1 to `maxMove`, and in each iteration, we calculate the number of ways to reach each cell using the results from the previous iteration. This approach can be space-optimized because calculating the state for `k` moves only requires the state from `k-1` moves.
**Time:** O(maxMove * m * n). We have a loop for `maxMove`, and inside it, we iterate through the `m * n` grid. · **Space:** O(m * n). We use two 2D arrays of size `m * n` to store the DP states for the current and next move.
**Pros:** Most efficient in terms of both time and space.; Avoids recursion overhead and potential stack overflow issues.; Optimal space complexity for this problem.
**Cons:** The logic can be slightly more complex to grasp compared to the direct recursive translation.
### Explanation
Let `dp[i][j]` be the number of ways to reach cell `(i, j)` after a certain number of moves.

- We start with `dp[startRow][startColumn] = 1` and all other `dp` entries as 0, representing the state before any moves.
- We then iterate from `k = 1` to `maxMove`. In each iteration `k`, we compute a new DP table, `temp[m][n]`, representing the number of ways to reach each cell in exactly `k` moves.
- For each cell `(i, j)`, `temp[i][j]` is the sum of the number of ways to reach its neighbors in `k-1` moves.
- While iterating, if a move from a cell `(i, j)` leads out of bounds, we add the number of ways to reach `(i, j)` (`dp[i][j]`) to our total `count` of out-of-boundary paths.
- After each full iteration over the grid for a given number of moves `k`, we replace the `dp` table with the `temp` table for the next iteration.
- This space optimization reduces the DP table from 3D (`O(maxMove * m * n)`) to 2D (`O(m * n)`).
```java
class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int MOD = 1000000007;
        int[][] dp = new int[m][n];
        dp[startRow][startColumn] = 1;
        int count = 0;

        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        for (int moves = 1; moves <= maxMove; moves++) {
            int[][] temp = new int[m][n];
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (dp[i][j] > 0) {
                        for (int[] d : dirs) {
                            int ni = i + d[0];
                            int nj = j + d[1];

                            if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
                                count = (count + dp[i][j]) % MOD;
                            } else {
                                temp[ni][nj] = (temp[ni][nj] + dp[i][j]) % MOD;
                            }
                        }
                    }
                }
            }
            dp = temp;
        }

        return count;
    }
}
```
### Algorithm
- `1. Initialize a 2D array `dp[m][n]` with zeros, and set `dp[startRow][startColumn] = 1`.`
- `2. Initialize a variable `count = 0` to store the number of out-of-boundary paths.`
- `3. Loop for `moves` from 1 to `maxMove`.`
- `4. Inside the loop, create a temporary 2D array `temp[m][n]` initialized to zeros.`
- `5. Iterate through each cell `(i, j)` of the grid.`
- `6. If `dp[i][j] > 0`, it means there are paths to this cell.`
- `7. For each of the four directions from `(i, j)`, calculate the next cell `(ni, nj)`.`
- `8. If `(ni, nj)` is out of bounds, add `dp[i][j]` to `count` (with modulo).`
- `9. If `(ni, nj)` is in bounds, add `dp[i][j]` to `temp[ni][nj]` (with modulo).`
- `10. After iterating through all cells, update `dp = temp`.`
- `11. After the main loop finishes, return `count`.`

# Solutions
### Java

```java
class Solution {
private
  int m;
private
  int n;
private
  int[][][] f;
private
  static final int[] DIRS = {-1, 0, 1, 0, -1};
private
  static final int MOD = (int)1 e9 + 7;
public
  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    this.m = m;
    this.n = n;
    f = new int[m + 1][n + 1][maxMove + 1];
    for (var a : f) {
      for (var b : a) {
        Arrays.fill(b, -1);
      }
    }
    return dfs(startRow, startColumn, maxMove);
  }
private
  int dfs(int i, int j, int k) {
    if (i < 0 || i >= m || j < 0 || j >= n) {
      return 1;
    }
    if (f[i][j][k] != -1) {
      return f[i][j][k];
    }
    if (k == 0) {
      return 0;
    }
    int res = 0;
    for (int t = 0; t < 4; ++t) {
      int x = i + DIRS[t];
      int y = j + DIRS[t + 1];
      res += dfs(x, y, k - 1);
      res %= MOD;
    }
    f[i][j][k] = res;
    return res;
  }
}

```

### Python

```python
class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int: @ cache def dfs(i, j, k): if i < 0 or j < 0 or i >= m or j >= n: return 1 if k <= 0: return 0 res = 0 for a, b in [[- 1, 0], [1, 0], [0, 1], [0, - 1]]: x, y = i + a, j + b res += dfs(x, y, k - 1) res %= mod return res mod = 10 ** 9 + 7 return dfs(startRow, startColumn, maxMove)

```

### CPP

```cpp
class Solution {
public:
  int m;
  int n;
  const int mod = 1e9 + 7;
  int f[51][51][51];
  int dirs[5] = {-1, 0, 1, 0, -1};
  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    memset(f, 0xff, sizeof(f));
    this->m = m;
    this->n = n;
    return dfs(startRow, startColumn, maxMove);
  }
  int dfs(int i, int j, int k) {
    if (i < 0 || i >= m || j < 0 || j >= n)
      return 1;
    if (f[i][j][k] != -1)
      return f[i][j][k];
    if (k == 0)
      return 0;
    int res = 0;
    for (int t = 0; t < 4; ++t) {
      int x = i + dirs[t], y = j + dirs[t + 1];
      res += dfs(x, y, k - 1);
      res %= mod;
    }
    f[i][j][k] = res;
    return res;
  }
};

```