An Interest In:
Web News this Week
- April 20, 2024
- April 19, 2024
- April 18, 2024
- April 17, 2024
- April 16, 2024
- April 15, 2024
- April 14, 2024
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
xn
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 mostmaxMove
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 modulo10^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; }};
Original Link: https://dev.to/seanpgallivan/solution-out-of-boundary-paths-2jef
Dev To
An online community for sharing and discovering great ideas, having debates, and making friendsMore About this Source Visit Dev To