Watch 10 video solutions for Out of Boundary Paths, a medium level problem involving Dynamic Programming. This walkthrough by NeetCodeIO has 16,625 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 < nProblem 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 | 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 |