LeetCode 576: Out of Boundary Paths

Problem Restatement

We are given an m x n grid and a ball starting at position [startRow, startColumn].

On each move, the ball can move one cell in one of four directions:

up, down, left, right

The ball may also move outside the grid. We can use at most maxMove moves.

Return the number of different paths that move the ball out of the grid boundary. Since the answer may be large, return it modulo 10^9 + 7.

Input and Output

Constraints:

Examples

Example 1:

m = 2
n = 2
maxMove = 2
startRow = 0
startColumn = 0

Output:

6

The ball starts at the top-left corner. Some paths leave immediately by moving up or left. Other paths stay inside for one move and leave on the second move.

Example 2:

m = 1
n = 3
maxMove = 3
startRow = 0
startColumn = 1

Output:

12

The grid has only one row, so moving up or down exits the grid immediately.

First Thought: Brute Force

A direct solution is to try every possible sequence of moves.

At each step, there are four choices:

up, down, left, right

So with maxMove moves, the number of possible move sequences can be as large as:

4^maxMove

Since maxMove can be 50, this is far too large.

Key Insight

Many paths reach the same state.

A state is determined by three values:

(row, column, moves_left)

For example, if we are at cell (1, 2) with 5 moves left, the number of ways to eventually leave the grid is always the same. It does not matter how we arrived there.

So we can define:

dp(row, col, moves_left)

as the number of paths that move the ball out of the grid, starting from (row, col) with moves_left moves remaining.

This gives us a recursive dynamic programming problem.

Recurrence

If the ball is already outside the grid, then we found one valid path:

return 1

If the ball is still inside the grid but no moves remain, then this path failed to leave:

return 0

Otherwise, try the four possible moves:

dp(row, col, moves_left)
=
dp(row + 1, col, moves_left - 1)
+ dp(row - 1, col, moves_left - 1)
+ dp(row, col + 1, moves_left - 1)
+ dp(row, col - 1, moves_left - 1)

Take the result modulo 10^9 + 7.

Algorithm

Use DFS with memoization.

1. Define a recursive function dfs(row, col, moves_left).
2. If (row, col) is outside the grid, return 1.
3. If moves_left == 0, return 0.
4. If this state was already computed, return the cached value.
5. Recursively try all four directions.
6. Store the result in the cache.
7. Return dfs(startRow, startColumn, maxMove).

Correctness

We prove that dfs(row, col, moves_left) returns the number of valid paths that move the ball out of the grid from the given state.

If (row, col) is outside the grid, the path has already crossed the boundary. This contributes exactly one valid path, so returning 1 is correct.

If (row, col) is inside the grid and moves_left == 0, no more moves are allowed. Since the ball has not left the grid, this contributes no valid path, so returning 0 is correct.

For any inside cell with at least one move left, every valid path must begin with exactly one of the four possible moves. After that first move, the number of valid completions is exactly the value of dfs on the next cell with one fewer move. These four sets of paths are disjoint because they have different first moves. Therefore, summing the four recursive results counts every valid path exactly once.

Memoization does not change the value being computed. It only reuses the result for a state that has already been solved.

Therefore, dfs(startRow, startColumn, maxMove) returns the required answer.

Complexity

Let:

K = maxMove

There are at most:

m * n * (K + 1)

states.

Each state tries four directions.

Implementation

from functools import cache

class Solution:
    def findPaths(
        self,
        m: int,
        n: int,
        maxMove: int,
        startRow: int,
        startColumn: int,
    ) -> int:
        MOD = 1_000_000_007

        @cache
        def dfs(row: int, col: int, moves_left: int) -> int:
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1

            if moves_left == 0:
                return 0

            total = 0
            total += dfs(row + 1, col, moves_left - 1)
            total += dfs(row - 1, col, moves_left - 1)
            total += dfs(row, col + 1, moves_left - 1)
            total += dfs(row, col - 1, moves_left - 1)

            return total % MOD

        return dfs(startRow, startColumn, maxMove)

Code Explanation

The constant:

MOD = 1_000_000_007

is required because the number of paths can be very large.

The cached function:

dfs(row, col, moves_left)

represents the number of ways to leave the grid from the current position with the given number of moves remaining.

This condition checks whether the ball has left the grid:

if row < 0 or row >= m or col < 0 or col >= n:
    return 1

Once the ball leaves, we count that path immediately.

This condition checks whether we are stuck inside the grid:

if moves_left == 0:
    return 0

If there are no moves left and the ball has not crossed the boundary, this path does not count.

Then we try all four directions:

total += dfs(row + 1, col, moves_left - 1)
total += dfs(row - 1, col, moves_left - 1)
total += dfs(row, col + 1, moves_left - 1)
total += dfs(row, col - 1, moves_left - 1)

Each recursive call uses one move.

Finally, we return:

return total % MOD

The cache ensures that each state is solved only once.

Testing

def run_tests():
    s = Solution()

    assert s.findPaths(2, 2, 2, 0, 0) == 6
    assert s.findPaths(1, 3, 3, 0, 1) == 12
    assert s.findPaths(1, 1, 0, 0, 0) == 0
    assert s.findPaths(1, 1, 1, 0, 0) == 4
    assert s.findPaths(2, 3, 1, 0, 1) == 1

    print("all tests passed")

run_tests()

Test meaning: