Out of Boundary Paths solution and explanation
9 more videos on this problem
Out of Boundary Paths - Leetcode 576 - PythonNeetCodeIO · 18:20 · 16K views
Out of Boundary Paths | Recursion | Memoization | Bottom Up | Optimal Bottom Up | Leetcode 576codestorywithMIK · 56:47 · 5K views
Out of Boundary Paths | Leetcode 576 | Live Coding session ⚽️⚽️⚽️Coding Decoded · 10:24 · 5K views
576. Out of Boundary Paths | Recursion - Memoization - Bottom Up - Bottom Up OptimisedAryan Mittal · 37:43 · 2K views
LeetCode 576. Out of Boundary PathsHappy Coding · 9:54 · 1K views
Out of Boundary Paths | LeetCode 576 | Coders CampCoders Camp · 8:36 · 1K views
Leetcode - Out of Boundary Paths (Python)Timothy H Chang · 5:55 · 1K views
LeetCode 576 Out of Boundary Pathschen xiang · 10:22 · 645 views
Leetcode | 576. Out of Boundary Paths | Medium | Java SolutionDeveloper Docs · 12:09 · 467 views
Out of Boundary Paths || Leetcode Medium #576 || Dynamic ProgrammingDigital Interview · 7:41 · 174 views
The 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:
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 <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n
Approach overview
Problem Overview: You are given an m x n grid and a starting cell. From each position you can move up, down, left, or right. The task is to count how many paths move the ball outside the grid boundary within at most maxMove steps. Because the number of paths grows quickly, the result must be returned modulo 1e9 + 7.
Approach 1: Depth-First Search with Memoization (O(m * n * maxMove) time, O(m * n * maxMove) space)
Model the problem as a recursive search where each state is defined by (row, col, remainingMoves). From a cell, recursively explore four directions. If the next move leaves the grid, count it as one valid path. If no moves remain while still inside the grid, the path contributes zero. Many states repeat during recursion, so cache results in a memoization table keyed by the state tuple. This eliminates exponential recomputation and reduces the complexity to O(m * n * maxMove). This approach closely follows the natural problem definition and is easy to implement using recursion with caching. It fits well when practicing Depth-First Search combined with memoization.
Approach 2: Dynamic Programming (Bottom-Up) (O(m * n * maxMove) time, O(m * n) space)
Instead of exploring recursively, build the solution iteratively. Let dp[i][j] represent the number of ways to reach cell (i, j) after the current number of moves. Start with the initial position having value 1. For each move from 1 to maxMove, compute a new grid by distributing paths from every cell to its four neighbors. If a move goes outside the grid, add that count to the final answer instead of storing it in the grid. After processing each step, replace the previous DP grid with the newly computed one. This simulation accumulates all ways the ball can leave the grid in up to maxMove steps. The approach is a standard layered transition used in Dynamic Programming problems where states depend on the previous step.
Recommended for interviews: The bottom-up dynamic programming solution is usually expected. It avoids recursion overhead, uses only O(m * n) memory, and clearly shows how states transition between moves. Discussing the DFS + memoization version first demonstrates understanding of overlapping subproblems, while converting it to iterative DP shows stronger algorithm design skills.
Approach 1: Dynamic Programming Approach
The main idea is to use a 3D dynamic programming array dp[i][j][k] where i and j represent the current position on the grid, and k represents the number of moves remaining. The value at dp[i][j][k] represents the number of ways to move the ball out of bounds using at most k moves starting from (i, j).
Transitions are made by moving the ball in one of the four possible directions and decreasing the move count. If the ball goes out of bounds, increment the path count. The answer is the sum of paths from startRow, startColumn using maxMove moves.
def findPaths(m, n, maxMove, startRow, startColumn):
MOD = 1000000007
dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]
dp[startRow][startColumn][0] = 1
count = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for move in range(1, maxMove + 1):
for i in range(m):
for j in range(n):
for d in directions:
ni, nj = i + d[0], j + d[1]
if ni < 0 or nj < 0 or ni >= m or nj >= n:
count = (count + dp[i][j][move-1]) % MOD
else:
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move-1]) % MOD
return count
print(findPaths(2, 2, 2, 0, 0)) # Output: 6
print(findPaths(1, 3, 3, 0, 1)) # Output: 12import java.util.Arrays;
class Solution {
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int MOD = 1000000007;
int[][][] dp = new int[m][n][maxMove + 1];
dp[startRow][startColumn][0] = 1;
int count = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int move = 1; move <= maxMove; move++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int[] d : directions) {
int ni = i + d[0];
int nj = j + d[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i][j][move-1]) % MOD;
} else {
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move-1]) % MOD;
}
}
}
}
}
return count;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findPaths(2, 2, 2, 0, 0)); // Output: 6
System.out.println(sol.findPaths(1, 3, 3, 0, 1)); // Output: 12
}
}#include <vector>
using namespace std;
class Solution {
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(maxMove + 1)));
int MOD = 1000000007;
vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
dp[startRow][startColumn][0] = 1;
int count = 0;
for (int move = 1; move <= maxMove; move++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (auto& d : directions) {
int ni = i + d[0];
int nj = j + d[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i][j][move-1]) % MOD;
} else {
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move-1]) % MOD;
}
}
}
}
}
return count;
}
};var findPaths = function(m, n, maxMove, startRow, startColumn) {
const MOD = 1000000007;
const dp = new Array(m).fill(0).map(() => new Array(n).fill(0).map(() => new Array(maxMove + 1).fill(0)));
dp[startRow][startColumn][0] = 1;
let count = 0;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let move = 1; move <= maxMove; move++) {
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
for (let [dx, dy] of directions) {
const ni = i + dx, nj = j + dy;
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i][j][move - 1]) % MOD;
} else {
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move - 1]) % MOD;
}
}
}
}
}
return count;
};
console.log(findPaths(2, 2, 2, 0, 0)); // Output: 6
console.log(findPaths(1, 3, 3, 0, 1)); // Output: 12;#include <stdio.h>
#define MOD 1000000007
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int dp[51][51][51] = {{{0}}};
int directions[4][2] = { {1, 0}, {-1, 0}, {0, 1}, {0, -1} };
dp[startRow][startColumn][0] = 1;
int count = 0;
for (int move = 1; move <= maxMove; move++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
for (int d = 0; d < 4; d++) {
int ni = i + directions[d][0];
int nj = j + directions[d][1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i][j][move-1]) % MOD;
} else {
dp[ni][nj][move] = (dp[ni][nj][move] + dp[i][j][move-1]) % MOD;
}
}
}
}
}
return count;
}
int main() {
printf("%d\n", findPaths(2, 2, 2, 0, 0)); // Output: 6
printf("%d\n", findPaths(1, 3, 3, 0, 1)); // Output: 12
return 0;
}using System;
public class Solution {
public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
int MOD = 1000000007;
int[,,] dp = new int[m, n, maxMove + 1];
dp[startRow, startColumn, 0] = 1;
int count = 0;
int[][] directions = new int[][] {
new int[] {1, 0}, new int[] {-1, 0}, new int[] {0, 1}, new int[] {0, -1}
};
for (int move = 1; move <= maxMove; move++) {
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
foreach (int[] d in directions) {
int ni = i + d[0];
int nj = j + d[1];
if (ni < 0 || nj < 0 || ni >= m || nj >= n) {
count = (count + dp[i, j, move - 1]) % MOD;
} else {
dp[ni, nj, move] = (dp[ni, nj, move] + dp[i, j, move - 1]) % MOD;
}
}
}
}
}
return count;
}
public static void Main() {
var solution = new Solution();
Console.WriteLine(solution.FindPaths(2, 2, 2, 0, 0)); // Output: 6
Console.WriteLine(solution.FindPaths(1, 3, 3, 0, 1)); // Output: 12
}
}The Python code executes a grid-based approach using dynamic programming. With every move, ball attempts all directions, updating paths to reach out of boundary efficiently. Variable count stores the modular path outcomes over the iterations.
Time Complexity: O(m * n * maxMove) reflecting the 3-layered iteration.
Space Complexity: O(m * n * maxMove) driven by the necessity to store data in the dp array.
Approach 2: Depth-First Search with Memorization
DFS with memoization is used to prevent recalculating results for already evaluated states by storing them in a map or dictionary. Each call is a recursive attempt to move in all directions from the current cell, decrementing the move count. Result of out-of-bounds attempts is stored so it can be reused, avoiding exponential time complexity.
This algorithm uses a function that considers the current position and remaining moves. For every call, explore in four possible directions and add to the path count if the ball gets out of bounds. Store already calculated counts in a dictionary for path optimization.
def findPaths(m, n, maxMove, startRow, startColumn):
MOD = 1000000007
memo = [[[-1] * (maxMove + 1) for _ in range(n)] for _ in range(m)]
def dfs(i, j, remainingMove):
if i < 0 or i >= m or j < 0 or j >= n:
return 1
if remainingMove == 0:
return 0
if memo[i][j][remainingMove] != -1:
return memo[i][j][remainingMove]
count = 0
for ni, nj in [(i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)]:
count = (count + dfs(ni, nj, remainingMove - 1)) % MOD
memo[i][j][remainingMove] = count
return count
return dfs(startRow, startColumn, maxMove)
print(findPaths(2, 2, 2, 0, 0)) # Output: 6
print(findPaths(1, 3, 3, 0, 1)) # Output: 12import java.util.Arrays;
class Solution {
private static final int MOD = 1000000007;
private int[][][] memo;
public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
memo = new int[m][n][maxMove + 1];
for (int[][] layer : memo) {
for (int[] rows : layer) {
Arrays.fill(rows, -1);
}
}
return dfs(m, n, maxMove, startRow, startColumn);
}
private int dfs(int m, int n, int maxMove, int row, int column) {
if (row < 0 || column < 0 || row >= m || column >= n) return 1;
if (maxMove == 0) return 0;
if (memo[row][column][maxMove] != -1) return memo[row][column][maxMove];
int result = 0;
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int[] d : directions) {
result = (result + dfs(m, n, maxMove - 1, row + d[0], column + d[1])) % MOD;
}
memo[row][column][maxMove] = result;
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
System.out.println(sol.findPaths(2, 2, 2, 0, 0)); // Output: 6
System.out.println(sol.findPaths(1, 3, 3, 0, 1)); // Output: 12
}
}#include <vector>
using namespace std;
class Solution {
vector<vector<vector<int>>> memo;
int MOD = 1000000007;
int dfs(int m, int n, int maxMove, int row, int column) {
if (row < 0 || column < 0 || row >= m || column >= n) return 1;
if (maxMove == 0) return 0;
if (memo[row][column][maxMove] != -1) return memo[row][column][maxMove];
int result = 0;
vector<vector<int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (auto& dir : directions) {
result = (result + dfs(m, n, maxMove - 1, row + dir[0], column + dir[1])) % MOD;
}
return memo[row][column][maxMove] = result;
}
public:
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
memo = vector<vector<vector<int>>>(m, vector<vector<int>>(n, vector<int>(maxMove + 1, -1)));
return dfs(m, n, maxMove, startRow, startColumn);
}
};const findPaths = function(m, n, maxMove, startRow, startColumn) {
const MOD = 1000000007;
const memo = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(maxMove + 1).fill(-1)));
const dfs = (i, j, remainingMove) => {
if (i < 0 || i >= m || j < 0 || j >= n) return 1;
if (remainingMove === 0) return 0;
if (memo[i][j][remainingMove] !== -1) return memo[i][j][remainingMove];
let count = 0;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (const [dx, dy] of directions) {
count = (count + dfs(i + dx, j + dy, remainingMove - 1)) % MOD;
}
memo[i][j][remainingMove] = count;
return count;
};
return dfs(startRow, startColumn, maxMove);
};
console.log(findPaths(2, 2, 2, 0, 0)); // Output: 6
console.log(findPaths(1, 3, 3, 0, 1)); // Output: 12;#include <stdio.h>
#define MOD 1000000007
int memo[51][51][51];
int dfs(int m, int n, int maxMove, int row, int column) {
if (row < 0 || column < 0 || row >= m || column >= n) return 1;
if (maxMove == 0) return 0;
if (memo[row][column][maxMove] != -1) return memo[row][column][maxMove];
int result = 0;
result = (result + dfs(m, n, maxMove - 1, row + 1, column)) % MOD;
result = (result + dfs(m, n, maxMove - 1, row - 1, column)) % MOD;
result = (result + dfs(m, n, maxMove - 1, row, column + 1)) % MOD;
result = (result + dfs(m, n, maxMove - 1, row, column - 1)) % MOD;
return memo[row][column][maxMove] = result;
}
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
for (int i = 0; i < 51; i++)
for (int j = 0; j < 51; j++)
for (int k = 0; k < 51; k++)
memo[i][j][k] = -1;
return dfs(m, n, maxMove, startRow, startColumn);
}
int main() {
printf("%d\n", findPaths(2, 2, 2, 0, 0)); // Output: 6
printf("%d\n", findPaths(1, 3, 3, 0, 1)); // Output: 12
return 0;
}using System;
public class Solution {
private const int MOD = 1000000007;
private int[,,] memo;
public int FindPaths(int m, int n, int maxMove, int startRow, int startColumn) {
memo = new int[m, n, maxMove + 1];
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
for (int k = 0; k <= maxMove; k++)
memo[i, j, k] = -1;
return Dfs(m, n, maxMove, startRow, startColumn);
}
private int Dfs(int m, int n, int move, int row, int col) {
if (row < 0 || row >= m || col < 0 || col >= n) return 1;
if (move == 0) return 0;
if (memo[row, col, move] != -1) return memo[row, col, move];
int result = 0;
int[][] directions = new [] { new []{1, 0}, new []{-1, 0}, new []{0, 1}, new []{0, -1} };
foreach (var dir in directions) {
result = (result + Dfs(m, n, move - 1, row + dir[0], col + dir[1])) % MOD;
}
memo[row, col, move] = result;
return result;
}
public static void Main() {
Solution solution = new Solution();
Console.WriteLine(solution.FindPaths(2, 2, 2, 0, 0)); // Output: 6
Console.WriteLine(solution.FindPaths(1, 3, 3, 0, 1)); // Output: 12
}
}The Python implementation exemplifies a recursive depth-first approach with memoization storing processed outcomes to minimize repetition. During each recursive call, all directional movements are attemptively calculated leading to the cumulative boundary escape paths.
Time Complexity: O(m * n * maxMove) by invoking each unique state once only.
Space Complexity: O(m * n * maxMove) associated with memoization of evolutionary steps.
Approach 3: Memoization Search
We define a function dfs(i, j, k) to represent the number of paths that can move out of the boundary starting from coordinates (i, j) with k steps remaining.
In the function dfs(i, j, k), we first handle the boundary cases. If the current coordinates (i, j) are out of the grid range, return 1 if k geq 0, otherwise return 0. If k leq 0, it means we are still within the grid but have no remaining moves, so return 0. Next, we iterate over the four directions, move to the next coordinates (x, y), then recursively call dfs(x, y, k - 1), and accumulate the results to the answer.
In the main function, we call dfs(startRow, startColumn, maxMove), which represents the number of paths that can move out of the boundary starting from the initial coordinates (startRow, startColumn) with maxMove steps remaining.
To avoid redundant calculations, we can use memoization.
The time complexity is O(m times n times k), and the space complexity is O(m times n times k). Here, m and n are the number of rows and columns of the grid, and k is the number of steps that can be moved, with k = maxMove leq 50.
function findPaths(
m: number,
n: number,
maxMove: number,
startRow: number,
startColumn: number,
): number {
const f = Array.from({ length: m }, () =>
Array.from({ length: n }, () => Array(maxMove + 1).fill(-1)),
);
const mod = 1000000007;
const dirs = [-1, 0, 1, 0, -1];
const dfs = (i: number, j: number, k: number): number => {
if (i < 0 || i >= m || j < 0 || j >= n) {
return k >= 0 ? 1 : 0;
}
if (k <= 0) {
return 0;
}
if (f[i][j][k] !== -1) {
return f[i][j][k];
}
let ans = 0;
for (let d = 0; d < 4; ++d) {
const [x, y] = [i + dirs[d], j + dirs[d + 1]];
ans = (ans + dfs(x, y, k - 1)) % mod;
}
return (f[i][j][k] = ans);
};
return dfs(startRow, startColumn, maxMove);
}func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
f := make([][][]int, m)
for i := range f {
f[i] = make([][]int, n)
for j := range f[i] {
f[i][j] = make([]int, maxMove+1)
for k := range f[i][j] {
f[i][j][k] = -1
}
}
}
const mod int = 1e9 + 7
var dfs func(int, int, int) int
dirs := [5]int{-1, 0, 1, 0, -1}
dfs = func(i, j, k int) int {
if i < 0 || i >= m || j < 0 || j >= n {
if k >= 0 {
return 1
}
return 0
}
if k <= 0 {
return 0
}
if f[i][j][k] != -1 {
return f[i][j][k]
}
ans := 0
for d := 0; d < 4; d++ {
x, y := i+dirs[d], j+dirs[d+1]
ans = (ans + dfs(x, y, k-1)) % mod
}
f[i][j][k] = ans
return ans
}
return dfs(startRow, startColumn, maxMove)
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n * maxMove) reflecting the 3-layered iteration. |
| Depth-First Search with Memorization | Time Complexity: O(m * n * maxMove) by invoking each unique state once only. |
| Memoization Search | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Depth-First Search with Memoization | O(m * n * maxMove) | O(m * n * maxMove) | When starting from a recursive formulation and converting overlapping subproblems into cached states |
| Dynamic Programming (Bottom-Up) | O(m * n * maxMove) | O(m * n) | Preferred interview solution and best for iterative simulation of moves with reduced memory |
Frequently asked questions
Is Out of Boundary Paths easy or hard?
Out of Boundary Paths is rated Medium difficulty on LeetCode. The challenge comes from recognizing overlapping subproblems and modeling the grid transitions using dynamic programming rather than exploring all paths naively.
Out of Boundary Paths Python/Java solution
Python and Java implementations typically use either a 3D memoization cache for DFS or a 2D DP grid updated for each move. Both approaches follow the same transition logic and apply modulo 1e9+7 to keep numbers within bounds.
What is the best approach for Out of Boundary Paths?
Dynamic Programming with step-by-step state transitions is the most practical approach. It tracks how many ways the ball reaches each cell after every move and accumulates paths that exit the grid. The complexity is O(m * n * maxMove) time and O(m * n) space.
Is Out of Boundary Paths asked at Google/Amazon/Meta?
Grid dynamic programming problems like this commonly appear in interviews at companies such as Amazon, Google, and Microsoft. The question tests understanding of state transitions, boundary conditions, and optimization using memoization or DP.
What data structure is used in Out of Boundary Paths?
The core data structure is a 2D dynamic programming array representing the grid. In the memoized DFS version, a hash map or 3D array caches results for (row, column, remainingMoves) states to avoid repeated computation.
What is the time complexity of Out of Boundary Paths?
Both the memoized DFS and bottom-up dynamic programming solutions run in O(m * n * maxMove) time. Each state defined by grid position and remaining moves is computed once, and each state explores four directions.
How to solve Out of Boundary Paths in O(m * n * maxMove)?
Use dynamic programming where dp[i][j] represents the number of ways to reach cell (i, j) at the current step. For each move, distribute counts to four neighbors and add contributions that leave the grid to the result. Repeating this for maxMove steps processes all possible paths efficiently.