Solution: Out of Boundary Paths
Tags: algorithms, javascript, java, python
Published: 2021-06-24 09:08:36

*This is part of a series of Leetcode solution explanations ([index](https://dev.to/seanpgallivan/leetcode-solutions-index-57fl)). If you liked this solution or found it useful,* ***please like*** *this post and/or* ***upvote*** *[my solution post on Leetcode's forums](https://leetcode.com/problems/out-of-boundary-paths/discuss/1293798).*

---

#### [Leetcode Problem #576 (*Medium*): Out of Boundary Paths](https://leetcode.com/problems/out-of-boundary-paths/)

---

#### ***Description:***

<br />(*Jump to*: [*Solution Idea*](#idea) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

>
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 four 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** `10^9 + 7`.

---

#### ***Examples:***
>
Example 1:||
|---:|---|
Input:| m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output:| 6
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_1.png)
>
Example 2:||
|---:|---|
Input:| m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output:| 12
Visual:|![Example 1 Visual](https://assets.leetcode.com/uploads/2021/04/28/out_of_boundary_paths_2.png)

---

#### ***Constraints:***
>
 - `1 <= m, n <= 50`
 - `0 <= maxMove <= 50`
 - `0 <= startRow <= m`
 - `0 <= startColumn <= n`

---

#### ***Idea:***

<br />(*Jump to*: [*Problem Description*](#description) || *Code*: [*JavaScript*](#javascript-code) | [*Python*](#python-code) | [*Java*](#java-code) | [*C++*](#c-code))

A brute force solution for this problem would be far too long since the number of possible paths is **4^maxMove**. As is the case for most problems that contain overlapping paths, this problem can be simplified by combining these overlapping paths with the help of a **dynamic programming** (**DP**) approach.

In this instance, we can create a DP matrix in which each cell (**dp[d][i][j]**) represents the solution where **d** is the number of moves remaining and **i** and **j** are the coordinates of the starting location. We can then build this DP matrix up from **d = 1** all the way up to **d = maxMove**.

To build up **dp**, we can start by filling in the starting values when **d = 1**, at which point each of the cells along the edges is a **1** and each corner is a **2**. From there, we can iterate through the remaining values for **d**, and each cell will be the sum of the surrounding four cells from the previous move iteration (**d-1**), as those cells correspond to the possible previous positions before moving to the current cell.

Since we want to include any path that doesn't take up the full **maxMove**, the solution (**ans**) will then be the sum of the cells in **dp** that correspond to **i = startRow** and **j = startColumn** with all possible values for **d**.

To make things easier by preventing the need for out-of-bounds checks, we can add a buffer row/column on all four sides of the grid representations in **dp** filled with **0** values.

As we only ever use the previous iteration of **d** to build the current one, we can save space in this solution by compressing **dp** into only two 2D matrices (**dpCurr, dpLast**) instead of a 3D matrix of **maxMove** depth. We can do this by just swapping **dpCurr** and **dpLast** between each iteration and overwriting the old values in **dpCurr** as we iterate through. We can also then keep track of **ans** as we go.

We should also not forget to use the **modulo** operation on each cell value equation.

 - _**Time Complexity: O(N * M * L)** where **N** and **M** are the dimensions of the grid and **L** is the maximum number of moves_
 - _**Space Complexity: O(N * M)** for the DP matrices_

---

#### ***Javascript Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```javascript
var findPaths = function(m, n, maxMove, startRow, startColumn) {
    if (!maxMove) return 0
    let dpCurr = Array.from({length: m+2}, () => new Uint32Array(n+2)),
        dpLast = Array.from({length: m+2}, () => new Uint32Array(n+2))
    for (let i = 1; i <= m; i++)
        dpCurr[i][1]++, dpCurr[i][n]++
    for (let j = 1; j <= n; j++)
        dpCurr[1][j]++, dpCurr[m][j]++
    let ans = dpCurr[startRow+1][startColumn+1]
    for (let d = 1; d < maxMove; d++) {
        [dpCurr, dpLast] = [dpLast, dpCurr]
        for (let i = 1; i <= m; i++)
            for (let j = 1; j <= n; j++)
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
        ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
    }
    return ans
};
```

---

#### ***Python Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```python
class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        if maxMove == 0: return 0
        dpCurr = [[0] * (n+2) for _ in range(m+2)]
        dpLast = [[0] * (n+2) for _ in range(m+2)]
        for i in range(1, m+1):
            dpCurr[i][1] += 1
            dpCurr[i][n] += 1
        for j in range(1, n+1):
            dpCurr[1][j] += 1
            dpCurr[m][j] += 1
        ans = dpCurr[startRow+1][startColumn+1]
        for d in range(maxMove-1):
            dpCurr, dpLast = dpLast, dpCurr
            for i, j in product(range(1, m+1), range(1, n+1)):
                dpCurr[i][j] = (dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007
        return ans
```

---

#### ***Java Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```java
class Solution {
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (maxMove == 0) return 0;
        int[][] dpCurr = new int[m+2][n+2], dpLast = new int[m+2][n+2];
        for (int i = 1; i <= m; i++) {
            dpCurr[i][1]++;
            dpCurr[i][n]++;
        }
        for (int j = 1; j <= n; j++) {
            dpCurr[1][j]++;
            dpCurr[m][j]++;
        }
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            int[][] temp = dpCurr;
            dpCurr = dpLast;
            dpLast = temp;
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
}
```

---

#### ***C++ Code:***
<br />(*Jump to*: [*Problem Description*](#description) || [*Solution Idea*](#idea))
```c++
class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        if (!maxMove) return 0;
        vector<vector<int>> dpCurr(m+2, vector<int>(n+2)),
            dpLast(m+2, vector<int>(n+2));
        for (int i = 1; i <= m; i++)
            dpCurr[i][1]++, dpCurr[i][n]++;
        for (int j = 1; j <= n; j++)
            dpCurr[1][j]++, dpCurr[m][j]++;
        int ans = dpCurr[startRow+1][startColumn+1];
        for (int d = 1; d < maxMove; d++) {
            dpCurr.swap(dpLast);
            for (int i = 1; i <= m; i++)
                for (int j = 1; j <= n; j++)
                    dpCurr[i][j] = (int)(((long)dpLast[i-1][j] + dpLast[i+1][j] + dpLast[i][j-1] + dpLast[i][j+1]) % 1000000007L);
            ans = (ans + dpCurr[startRow+1][startColumn+1]) % 1000000007;
        }
        return ans;
    }
};
```