In this guide, you will get 576. Out of Boundary Paths LeetCode Solution with the best time and space complexity. The solution to Out of Boundary Paths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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:
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
Example 2:
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
Complexity Analysis
Time Complexity: O(mnN)
Space Complexity: O(mnN)
576. Out of Boundary Paths LeetCode Solution in C++
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
vector<vector<vector<int>>> mem(maxMove + 1,
vector<vector<int>>(m, vector<int>(n, -1)));
return findPaths(m, n, maxMove, startRow, startColumn, mem);
}
private:
static constexpr int kMod = 1'000'000'007;
// Returns the number of paths to move the ball at (i, j) out-of-bounds with k
// moves.
int findPaths(int m, int n, int k, int i, int j,
vector<vector<vector<int>>>& mem) {
if (i < 0 || i == m || j < 0 || j == n)
return 1;
if (k == 0)
return 0;
if (mem[k][i][j] != -1)
return mem[k][i][j];
return mem[k][i][j] = (findPaths(m, n, k - 1, i + 1, j, mem) * 1L +
findPaths(m, n, k - 1, i - 1, j, mem) +
findPaths(m, n, k - 1, i, j + 1, mem) +
findPaths(m, n, k - 1, i, j - 1, mem)) %
kMod;
}
}; /* code provided by PROGIEZ */
576. Out of Boundary Paths LeetCode Solution in Java
class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
Integer[][][] mem = new Integer[maxMove + 1][m][n];
return findPaths(m, n, maxMove, startRow, startColumn, mem);
}
private static final int kMod = 1_000_000_007;
// Returns the number of paths to move the ball at (i, j) out-of-bounds with k
// moves.
private int findPaths(int m, int n, int k, int i, int j, Integer[][][] mem) {
if (i < 0 || i == m || j < 0 || j == n)
return 1;
if (k == 0)
return 0;
if (mem[k][i][j] != null)
return mem[k][i][j];
return mem[k][i][j] = (int) ((findPaths(m, n, k - 1, i + 1, j, mem) * 1L +
findPaths(m, n, k - 1, i - 1, j, mem) +
findPaths(m, n, k - 1, i, j + 1, mem) +
findPaths(m, n, k - 1, i, j - 1, mem)) %
kMod);
}
} // code provided by PROGIEZ
576. Out of Boundary Paths LeetCode Solution in Python
class Solution:
def findPaths(self, m, n, maxMove, startRow, startColumn):
kMod = 1000000007
@functools.lru_cache(None)
def dp(k: int, i: int, j: int) -> int:
"""
Returns the number of paths to move the ball at (i, j) out-of-bounds with
k moves.
"""
if i < 0 or i == m or j < 0 or j == n:
return 1
if k == 0:
return 0
return (dp(k - 1, i + 1, j) + dp(k - 1, i - 1, j) +
dp(k - 1, i, j + 1) + dp(k - 1, i, j - 1)) % kMod
return dp(maxMove, startRow, startColumn) # code by PROGIEZ
