Scale Engineer

Out of Boundary Paths

Med
#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
Patterns
Dynamic Programming
Companies
Baidu

Prompt

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 <= 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.
    • paths = findPaths(row-1, col, movesLeft-1) + findPaths(row+1, col, movesLeft-1) + findPaths(row, col-1, movesLeft-1) + findPaths(row, col+1, 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).
class Solution {    int MOD = 1000000007;    int m, n;     public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {        this.m = m;        this.n = n;        return solve(startRow, startColumn, maxMove);    }     private int solve(int r, int c, int moves) {        // Base case: moved out of bounds        if (r < 0 || r >= m || c < 0 || c >= n) {            return 1;        }        // Base case: no moves left        if (moves == 0) {            return 0;        }         long paths = 0;        // Move up        paths = (paths + solve(r - 1, c, moves - 1)) % MOD;        // Move down        paths = (paths + solve(r + 1, c, moves - 1)) % MOD;        // Move left        paths = (paths + solve(r, c - 1, moves - 1)) % MOD;        // Move right        paths = (paths + solve(r, c + 1, moves - 1)) % MOD;         return (int) paths;    }}

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.

Solutions

class Solution {private  int m;private  int n;private  int[][][] f;private  static final int[] DIRS = {-1, 0, 1, 0, -1};private  static final int MOD = (int)1 e9 + 7;public  int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {    this.m = m;    this.n = n;    f = new int[m + 1][n + 1][maxMove + 1];    for (var a : f) {      for (var b : a) {        Arrays.fill(b, -1);      }    }    return dfs(startRow, startColumn, maxMove);  }private  int dfs(int i, int j, int k) {    if (i < 0 || i >= m || j < 0 || j >= n) {      return 1;    }    if (f[i][j][k] != -1) {      return f[i][j][k];    }    if (k == 0) {      return 0;    }    int res = 0;    for (int t = 0; t < 4; ++t) {      int x = i + DIRS[t];      int y = j + DIRS[t + 1];      res += dfs(x, y, k - 1);      res %= MOD;    }    f[i][j][k] = res;    return res;  }}

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.

← Previous

Previous problem

Next →

Next problem