Out of Boundary Paths

Problem Description

We are given an m x n grid with a ball placed at position [startRow, startColumn]. The ball can move in four directions (up, down, left, right). We are allowed a maximum of maxMove moves. The goal is to find the number of paths that result in the ball moving out of the grid boundary. Since the answer can be huge, return the result modulo 10^9 + 7.

Key Insights

• Use Dynamic Programming (DP) as the state is defined by (current row, current column, moves remaining).
• Transitions are made from a cell to its four adjacent cells.
• If the ball moves out of bounds, it contributes to one valid path.
• States can be memoized to avoid recomputation and optimize the recursive solution.

Space and Time Complexity

Time Complexity: O(maxMove * m * n), since we compute each state at most once. Space Complexity: O(maxMove * m * n) for the memoization table.

Solution

We use a recursive dynamic programming (or memoization) approach. Define a function dp(i, j, movesLeft) that returns the number of ways to move out of bounds starting from cell (i, j) with movesLeft moves remaining. For each move from the current cell, check:

1. If the cell is out of bounds, return 1 (base case).
2. If no moves are left (movesLeft == 0) and we are still inside, return 0.
3. Otherwise, use recursion to explore all four directions and sum the paths. Store results in a memoization table to avoid recomputation, then return the computed value modulo 10^9 + 7.

Code Solutions