Solution: Out of Boundary Paths

This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.

Leetcode Problem #576 (Medium): Out of Boundary Paths

Description:

(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)

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 2:
Input:	m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output:	12
Visual:

Constraints:

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

Idea:

(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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:

(Jump to: Problem Description || Solution Idea)

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