Out of Boundary Paths - Solution & Explanation
Problem Statement
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.
This C solution initializes a 3D DP array to store the number of paths achieving out-of-bounds through various moves. It iterates over possible moves and transitions the current position to its adjacent cells, checking for out-of-bound conditions to increment the path count. The results are accumulated for all cells and moves.
Complexity
Time Complexity: O(m * n * maxMove) as each grid cell and move combination is processed exactly once.
Space Complexity: O(m * n * maxMove) due to the storage of 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.
This C solution initializes a memo array for caching recursive calls. The dfs function recursively explores all four movement directions. When the ball falls out of bounds, it contributes to the path count. Memoization avoids repeated calculations, ensuring efficiency.
Complexity
Time Complexity: O(m * n * maxMove) where each state is visited only once.
Space Complexity: O(m * n * maxMove) due to memoization storage.
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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming Approach | Time Complexity: O(m * n * maxMove) as each grid cell and move combination is processed exactly once. |
| Depth-First Search with Memorization | Time Complexity: O(m * n * maxMove) where each state is visited only once. |
| Memoization Search | — |
Detailed 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 |
Video Solution
Out of Boundary Paths - Leetcode 576 - Python • NeetCodeIO • 16,748 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Out of Boundary Paths easy or hard?
Out of Boundary Paths Python/Java solution
What is the best approach for Out of Boundary Paths?
Is Out of Boundary Paths asked at Google/Amazon/Meta?
What data structure is used in Out of Boundary Paths?
What is the time complexity of Out of Boundary Paths?
How to solve Out of Boundary Paths in O(m * n * maxMove)?
Ready to solve this problem?
Practice Out of Boundary Paths with our built-in code editor and test cases.
Practice on FleetCode