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 < nThe key idea in #576 Out of Boundary Paths is to count how many ways a ball can move outside an m x n grid within a limited number of moves. A brute-force DFS would explore all possible directions at each step, but this quickly becomes inefficient due to repeated subproblems.
A better approach uses Dynamic Programming with memoization. For each cell and remaining number of moves, we store the number of ways the ball can exit the grid. At every step, the ball can move in four directions (up, down, left, right). If a move leads outside the grid, it contributes to the count. Otherwise, we recursively compute the result for the next cell with one fewer move.
Because the same states appear many times, caching results significantly reduces recomputation. A bottom-up DP version can also be used where each layer represents paths reachable with a certain number of moves. The final result is typically computed modulo 1e9+7. This reduces the complexity to manageable levels for interview constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming (Memoization) | O(m × n × maxMove) | O(m × n × maxMove) |
| Bottom-Up DP with Rolling Grid | O(m × n × maxMove) | O(m × n) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
Is traversing every path feasible? There are many possible paths for a small matrix. Try to optimize it.
Can we use some space to store the number of paths and update them after every move?
One obvious thing: the ball will go out of the boundary only by crossing it. Also, there is only one possible way the ball can go out of the boundary from the boundary cell except for corner cells. From the corner cell, the ball can go out in two different ways. Can you use this thing to solve the problem?
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.
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.
1var findPaths = function(m, n, maxMove, startRow, startColumn) {
2 const MOD = 1000000007;
3
In this JavaScript solution, we use triple nested arrays to record and retrieve path results dynamically. It operates over a given number of moves systematically. The pathways out of bounds are counted with consideration of potential large number modulus.
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.
Time Complexity: O(m * n * maxMove) where each state is visited only once.
Space Complexity: O(m * n * maxMove) due to memoization storage.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of grid traversal and Dynamic Programming problems like this appear in FAANG-style interviews. They test understanding of state transitions, memoization, and efficient handling of exponential search spaces.
The optimal approach uses Dynamic Programming with memoization or bottom-up DP. By storing results for each grid cell and remaining move count, we avoid recomputing overlapping subproblems and significantly reduce runtime.
A multi-dimensional DP array or memoization cache is commonly used. It stores the number of ways to reach the boundary from a given cell with a specific number of remaining moves.
The problem contains overlapping subproblems because the number of ways to exit from a cell with a certain number of moves is reused multiple times. Dynamic Programming stores these results so they can be reused efficiently.
The JavaScript implementation expands on DFS with the addition of memoization for recursive function optimization. Each progressive move in possible directions is checked, collecting results on encountering grid bounds, finally tabulating modular outcomes.