Problem Description

The Out of Boundary Paths problem asks you to determine how many different paths a ball can take to move out of a given grid boundary within a maximum number of moves.

• You are given a grid of size m x n.
• The ball starts at position (startRow, startColumn).
• In each move, you can move the ball one step in any of the four directions: up, down, left, or right.
• You are allowed at most maxMove moves.
• Each time the ball moves outside the grid boundary, it is considered a valid path.
• Your task is to count the total number of possible paths that move the ball out of the grid boundary within maxMove moves, starting from the initial position.
• Return the answer modulo 10^9 + 7 (to prevent integer overflow).

Key constraints:

• You may revisit a cell multiple times along a path.
• Each path ends as soon as the ball leaves the grid.
• Grid sizes and moves can be large, so efficiency is important.

Thought Process

At first glance, this problem seems like a classic backtracking or brute-force search: for each move, try all four possible directions, and if the ball leaves the grid, count that as a valid path.

However, with larger grid sizes and higher maxMove values, this approach quickly becomes infeasible because the number of possible paths grows exponentially.

To optimize, we need to avoid recalculating the number of paths for the same cell and remaining moves. This is a classic scenario for dynamic programming (DP), where we store results for subproblems (cell position and moves left) and reuse them when needed.

The key insight is that the number of ways to move out of the boundary from a certain cell with a certain number of moves left is independent of how we arrived at that cell. So, we can cache the results for each (row, col, remainingMoves) state.

Solution Approach

• State Definition: We define a DP function dp(row, col, movesLeft) as the number of ways to move out of the grid starting from (row, col) with movesLeft moves remaining.
• Base Cases:
  • If row or col is out of bounds, return 1 (since we have just left the grid).
  • If movesLeft is 0 and we are still in bounds, return 0 (no more moves, can't leave the grid).
• Recurrence Relation:
  • For each direction (up, down, left, right), recursively call dp for the next cell with movesLeft - 1.
  • Sum the results for all four directions.
• Memoization: Use a cache (such as a 3D array or a hash map) to store results for each (row, col, movesLeft) to avoid redundant computation.
• Modulo Operation: Since the answer can be very large, take mod = 10^9 + 7 at each step.
• Initialization: Start the recursion with dp(startRow, startColumn, maxMove).

This approach ensures we only compute each unique state once, reducing the overall time complexity dramatically.

Example Walkthrough

Example:
m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0

• Start at (0, 0) with 2 moves.
• First move options:
  • Up: (-1, 0) → out of bounds (1 path)
  • Down: (1, 0) → in bounds
  • Left: (0, -1) → out of bounds (1 path)
  • Right: (0, 1) → in bounds
• For in-bounds moves (down and right), with 1 move left, repeat the process:
  • (1, 0), 1 move left:
    • Down: (2, 0) → out of bounds (1 path)
    • Up: (0, 0) → in bounds
    • Left: (1, -1) → out of bounds (1 path)
    • Right: (1, 1) → in bounds
  • (0, 1), 1 move left:
    • Up: (-1, 1) → out of bounds (1 path)
    • Down: (1, 1) → in bounds
    • Left: (0, 0) → in bounds
    • Right: (0, 2) → out of bounds (1 path)
• Continue until no moves are left. Sum all the ways the ball leaves the grid.
• Final answer: 6

This example shows how the DP approach avoids recalculating the same subproblems.

Time and Space Complexity

• Brute-Force Approach:
  • Each move has 4 choices, leading to O(4^{maxMove}) possible paths.
  • Exponential growth makes this approach infeasible for large maxMove.
• DP with Memoization:
  • There are at most m * n * maxMove unique states.
  • Each state is computed once, and each computation takes constant time (4 recursive calls).
  • Time Complexity: O(m * n * maxMove)
  • Space Complexity: O(m * n * maxMove) for the memoization cache.

Summary

The key to solving the Out of Boundary Paths problem efficiently is recognizing overlapping subproblems and using dynamic programming with memoization. By caching the number of ways to leave the grid from each cell with a certain number of moves left, we avoid redundant calculations and achieve a solution that scales well even for large grids and move counts. This approach transforms an exponential-time brute-force solution into a manageable polynomial-time algorithm, making it both elegant and practical.

Code Implementation

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        from functools import lru_cache

        @lru_cache(maxsize=None)
        def dp(row, col, moves):
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1
            if moves == 0:
                return 0
            res = 0
            for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                res = (res + dp(row+dr, col+dc, moves-1)) % MOD
            return res

        return dp(startRow, startColumn, maxMove)
      

class Solution {
public:
    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        const int MOD = 1e9 + 7;
        vector<vector<vector<int>>> memo(m, vector<vector<int>>(n, vector<int>(maxMove + 1, -1)));
        
        function<int(int,int,int)> dp = [&](int row, int col, int moves) {
            if (row < 0 || row >= m || col < 0 || col >= n) return 1;
            if (moves == 0) return 0;
            if (memo[row][col][moves] != -1) return memo[row][col][moves];
            int res = 0;
            vector<pair<int,int>> dirs = {{-1,0},{1,0},{0,-1},{0,1}};
            for (auto &d : dirs) {
                res = (res + dp(row + d.first, col + d.second, moves - 1)) % MOD;
            }
            memo[row][col][moves] = res;
            return res;
        };
        return dp(startRow, startColumn, maxMove);
    }
};
      

class Solution {
    private static final int MOD = 1000000007;
    private int[][][] memo;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        memo = new int[m][n][maxMove + 1];
        for (int[][] layer : memo)
            for (int[] row : layer)
                java.util.Arrays.fill(row, -1);
        return dp(m, n, maxMove, startRow, startColumn);
    }

    private int dp(int m, int n, int moves, int row, int col) {
        if (row < 0 || row >= m || col < 0 || col >= n) return 1;
        if (moves == 0) return 0;
        if (memo[row][col][moves] != -1) return memo[row][col][moves];
        int res = 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        for (int[] d : dirs) {
            res = (res + dp(m, n, moves - 1, row + d[0], col + d[1])) % MOD;
        }
        memo[row][col][moves] = res;
        return res;
    }
}
      

var findPaths = function(m, n, maxMove, startRow, startColumn) {
    const MOD = 1e9 + 7;
    const memo = new Array(m).fill(0).map(() => 
        new Array(n).fill(0).map(() => 
            new Array(maxMove + 1).fill(-1)
        )
    );

    function dp(row, col, moves) {
        if (row < 0 || row >= m || col < 0 || col >= n) return 1;
        if (moves === 0) return 0;
        if (memo[row][col][moves] !== -1) return memo[row][col][moves];
        let res = 0;
        const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
        for (const [dr, dc] of dirs) {
            res = (res + dp(row + dr, col + dc, moves - 1)) % MOD;
        }
        memo[row][col][moves] = res;
        return res;
    }
    return dp(startRow, startColumn, maxMove);
};