#0555Time: O(4^maxMove). For each move, we branch into 4 possibilities. The depth of the recursion is `maxMove`.Space: O(maxMove). This is for the recursion stack depth.1 company
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 mostmaxMove 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 modulo109 + 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
Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a simple recursive function to explore all possible paths from the starting cell. For each cell and remaining number of moves, it recursively calls itself for all four adjacent cells. The base cases handle situations where the ball goes out of bounds (a valid path) or runs out of moves while inside the grid (an invalid path).
Algorithm
1. Define a recursive function solve(r, c, moves)that returns the number of paths to get out of bounds from(r, c)withmoves left.
2. Base Case 1: If (r, c) is out of bounds, return 1.
3. Base Case 2: If moves is 0, return 0.
4. Recursive Step: Sum the results of calling solvefor the four adjacent cells (up, down, left, right) withmoves - 1.
5. Apply modulo 10^9 + 7 at each addition.
6. The initial call is solve(startRow, startColumn, maxMove).
Walkthrough
We define a recursive function, say findPaths(row, col, movesLeft).
Base Cases:
If the current position (row, col) is outside the grid boundaries (row < 0, row >= m, col < 0, or col >= n), it means we have found one path out of the grid. We return 1.
If movesLeft is 0, we have no more moves left. Since we are still within the grid, this path does not lead out. We return 0.
Recursive Step:
From the current cell (row, col), we can move in four directions: up, down, left, and right.
The total number of paths is the sum of the paths from each of these four moves. We make a recursive call for each direction with movesLeft - 1.
We must apply the modulo 10^9 + 7 to the sum to prevent overflow.
The initial call to the function will be findPaths(startRow, startColumn, maxMove).
This method explores every possible path of length up to maxMove, leading to a large number of redundant calculations for the same state (row, col, movesLeft).
1class Solution {2 int MOD = 1000000007;3 int m, n;45 public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {6 this.m = m;7 this.n = n;8 return solve(startRow, startColumn, maxMove);9 }1011 private int solve(int r, int c, int moves) {12 // Base case: moved out of bounds13 if (r < 0 || r >= m || c < 0 || c >= n) {14 return 1;15 }16 // Base case: no moves left17 if (moves == 0) {18 return 0;19 }2021 long paths = 0;22 // Move up23 paths = (paths + solve(r - 1, c, moves - 1)) % MOD;24 // Move down25 paths = (paths + solve(r + 1, c, moves - 1)) % MOD;26 // Move left27 paths = (paths + solve(r, c - 1, moves - 1)) % MOD;28 // Move right29 paths = (paths + solve(r, c + 1, moves - 1)) % MOD;3031 return (int) paths;32 }33}
Complexity
Time
O(4^maxMove). For each move, we branch into 4 possibilities. The depth of the recursion is `maxMove`.
Space
O(maxMove). This is for the recursion stack depth.
Trade-offs
Pros
Simple to understand and implement.
Directly translates the problem's definition into code.
Cons
Extremely inefficient due to a massive number of overlapping subproblems.
Will result in a "Time Limit Exceeded" (TLE) error for the given constraints.
This approach improves upon the brute-force recursion by using memoization to store the results of subproblems. A 3D array memo[row][col][movesLeft] is used to cache the number of paths from cell (row, col) with movesLeft moves remaining. This avoids re-computation and drastically reduces the time complexity.
Algorithm
1. Create a 3D memoization table memo[m][n][maxMove + 1] and initialize it with a value indicating 'not computed' (e.g., null or -1).
2. Define a recursive function solve(r, c, moves).
3. Base Case 1: If (r, c) is out of bounds, return 1.
4. Base Case 2: If moves is 0, return 0.
5. Memoization Check: If memo[r][c][moves] is already computed, return its value.
6. Recursive Step: Sum the results of calling solvefor the four adjacent cells withmoves - 1.
7. Store the result in memo[r][c][moves] before returning.
8. The initial call is solve(startRow, startColumn, maxMove).
Walkthrough
The core idea is to recognize that the recursive function findPaths(row, col, movesLeft) is called multiple times with the same arguments. We can store the result of each unique call and reuse it when needed.
We use a 3D array, memo[m][n][maxMove + 1], to store the computed results. Each entry memo[r][c][k] will store the number of ways to move out of the grid from cell (r, c) with k moves.
We initialize this memoization table with a sentinel value (e.g., -1 or null) to indicate that the state has not been computed yet.
The recursive function is modified as follows:
Before computing the result for (r, c, moves), we first check if memo[r][c][moves] has already been computed. If it has, we return the stored value directly.
If not, we compute the result as in the brute-force approach.
Before returning, we store the computed result in memo[r][c][moves] for future use.
1class Solution {2 int MOD = 1000000007;3 int m, n;4 Integer[][][] memo;56 public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {7 this.m = m;8 this.n = n;9 this.memo = new Integer[m][n][maxMove + 1];10 return solve(startRow, startColumn, maxMove);11 }1213 private int solve(int r, int c, int moves) {14 // Base case: moved out of bounds15 if (r < 0 || r >= m || c < 0 || c >= n) {16 return 1;17 }18 // Base case: no moves left19 if (moves == 0) {20 return 0;21 }22 // Memoization check23 if (memo[r][c][moves] != null) {24 return memo[r][c][moves];25 }2627 long paths = 0;28 paths = (paths + solve(r - 1, c, moves - 1)) % MOD;29 paths = (paths + solve(r + 1, c, moves - 1)) % MOD;30 paths = (paths + solve(r, c - 1, moves - 1)) % MOD;31 paths = (paths + solve(r, c + 1, moves - 1)) % MOD;3233 // Store result in memo table34 memo[r][c][moves] = (int) paths;35 return memo[r][c][moves];36 }37}
Complexity
Time
O(m * n * maxMove). Each state `(row, col, movesLeft)` is computed only once. The number of states is `m * n * maxMove`.
Space
O(m * n * maxMove). This is for the memoization table. The recursion stack depth adds `O(maxMove)`.
Trade-offs
Pros
Significantly more efficient than brute-force.
Guaranteed to pass within the time limits for the given constraints.
Still maintains a relatively clear, recursive structure.
Cons
Uses significant space for the memoization table.
Can lead to a StackOverflowError for very deep recursion, although not an issue with the given constraints (maxMove <= 50).
This is the most efficient approach. It uses an iterative, bottom-up dynamic programming method. Instead of recursion, we build up the solution iteratively. We maintain a 2D DP table, dp[m][n], where dp[i][j] stores the number of ways to reach cell (i, j). We iterate from 1 to maxMove, and in each iteration, we calculate the number of ways to reach each cell using the results from the previous iteration. This approach can be space-optimized because calculating the state for k moves only requires the state from k-1 moves.
Algorithm
1. Initialize a 2D array dp[m][n]with zeros, and setdp[startRow][startColumn] = 1.
2. Initialize a variable count = 0 to store the number of out-of-boundary paths.
3. Loop for movesfrom 1 tomaxMove.
4. Inside the loop, create a temporary 2D array temp[m][n] initialized to zeros.
5. Iterate through each cell (i, j) of the grid.
6. If dp[i][j] > 0, it means there are paths to this cell.
7. For each of the four directions from (i, j), calculate the next cell (ni, nj).
8. If (ni, nj)is out of bounds, adddp[i][j]tocount (with modulo).
9. If (ni, nj)is in bounds, adddp[i][j]totemp[ni][nj] (with modulo).
10. After iterating through all cells, update dp = temp.
11. After the main loop finishes, return count.
Walkthrough
Let dp[i][j] be the number of ways to reach cell (i, j) after a certain number of moves.
We start with dp[startRow][startColumn] = 1 and all other dp entries as 0, representing the state before any moves.
We then iterate from k = 1 to maxMove. In each iteration k, we compute a new DP table, temp[m][n], representing the number of ways to reach each cell in exactly k moves.
For each cell (i, j), temp[i][j] is the sum of the number of ways to reach its neighbors in k-1 moves.
While iterating, if a move from a cell (i, j) leads out of bounds, we add the number of ways to reach (i, j) (dp[i][j]) to our total count of out-of-boundary paths.
After each full iteration over the grid for a given number of moves k, we replace the dp table with the temp table for the next iteration.
This space optimization reduces the DP table from 3D (O(maxMove * m * n)) to 2D (O(m * n)).
1class Solution {2 public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {3 int MOD = 1000000007;4 int[][] dp = new int[m][n];5 dp[startRow][startColumn] = 1;6 int count = 0;78 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};910 for (int moves = 1; moves <= maxMove; moves++) {11 int[][] temp = new int[m][n];12 for (int i = 0; i < m; i++) {13 for (int j = 0; j < n; j++) {14 if (dp[i][j] > 0) {15 for (int[] d : dirs) {16 int ni = i + d[0];17 int nj = j + d[1];1819 if (ni < 0 || ni >= m || nj < 0 || nj >= n) {20 count = (count + dp[i][j]) % MOD;21 } else {22 temp[ni][nj] = (temp[ni][nj] + dp[i][j]) % MOD;23 }24 }25 }26 }27 }28 dp = temp;29 }3031 return count;32 }33}
Complexity
Time
O(maxMove * m * n). We have a loop for `maxMove`, and inside it, we iterate through the `m * n` grid.
Space
O(m * n). We use two 2D arrays of size `m * n` to store the DP states for the current and next move.
Trade-offs
Pros
Most efficient in terms of both time and space.
Avoids recursion overhead and potential stack overflow issues.
Optimal space complexity for this problem.
Cons
The logic can be slightly more complex to grasp compared to the direct recursive translation.
Solutions
Solution
1class Solution {2private3 int m;4private5 int n;6private7 int[][][] f;8private9 static final int[] DIRS = {-1, 0, 1, 0, -1};10private11 static final int MOD = (int)1 e9 + 7;12public13 int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {14 this.m = m;15 this.n = n;16 f = new int[m + 1][n + 1][maxMove + 1];17 for (var a : f) {18 for (var b : a) {19 Arrays.fill(b, -1);20 }21 }22 return dfs(startRow, startColumn, maxMove);23 }24private25 int dfs(int i, int j, int k) {26 if (i < 0 || i >= m || j < 0 || j >= n) {27 return 1;28 }29 if (f[i][j][k] != -1) {30 return f[i][j][k];31 }32 if (k == 0) {33 return 0;34 }35 int res = 0;36 for (int t = 0; t < 4; ++t) {37 int x = i + DIRS[t];38 int y = j + DIRS[t + 1];39 res += dfs(x, y, k - 1);40 res %= MOD;41 }42 f[i][j][k] = res;43 return res;44 }45}
1class Solution:2 def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int: @ cache def dfs(i, j, k): if i < 0 or j < 0 or i >= m or j >= n: return 1 if k <= 0: return 0 res = 0 for a, b in [[- 1, 0], [1, 0], [0, 1], [0, - 1]]: x, y = i + a, j + b res += dfs(x, y, k - 1) res %= mod return res mod = 10 ** 9 + 7 return dfs(startRow, startColumn, maxMove)
1class Solution {2public:3 int m;4 int n;5 const int mod = 1e9 + 7;6 int f[51][51][51];7 int dirs[5] = {-1, 0, 1, 0, -1};8 int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {9 memset(f, 0xff, sizeof(f));10 this->m = m;11 this->n = n;12 return dfs(startRow, startColumn, maxMove);13 }14 int dfs(int i, int j, int k) {15 if (i < 0 || i >= m || j < 0 || j >= n)16 return 1;17 if (f[i][j][k] != -1)18 return f[i][j][k];19 if (k == 0)20 return 0;21 int res = 0;22 for (int t = 0; t < 4; ++t) {23 int x = i + dirs[t], y = j + dirs[t + 1];24 res += dfs(x, y, k - 1);25 res %= mod;26 }27 f[i][j][k] = res;28 return res;29 }30};
Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.
