LeetCode 576 - Out of Boundary Paths

This problem asks us to count how many different ways a ball can leave the boundaries of a grid within a limited number of moves.

leetcodemediumdynamic-programming

LeetCode Problem 576

Difficulty: 🟡 Medium
Topics: Dynamic Programming

Solution

Problem Understanding

This problem asks us to count how many different ways a ball can leave the boundaries of a grid within a limited number of moves.

We are given a grid of size m x n, where:

  • m is the number of rows

  • n is the number of columns

  • The ball starts at position (startRow, startColumn)

  • In one move, the ball can move:

  • up

  • down

  • left

  • right

The ball is allowed to cross the boundary of the grid. Once it leaves the grid, that path is considered successful and contributes to the final answer.

The key detail is that we may use at most maxMove moves. This means a path counts if the ball exits the grid in any number of moves from 1 up to maxMove.

The answer can become extremely large because every position can branch into four possible directions at every step. Because of this, the problem requires returning the answer modulo:

$10^9 + 7$

The constraints are important:

  • m, n <= 50
  • maxMove <= 50

A brute force recursive exploration would generate up to:

$4^{ ext{maxMove}}$

possible paths, which is far too large when maxMove = 50.

This immediately suggests that many subproblems repeat. For example, reaching the same cell with the same remaining moves will always produce the same number of future escape paths. That overlapping structure makes this a classic dynamic programming problem.

Several edge cases are important:

  • maxMove = 0, no movement is allowed, so the answer must be 0
  • Starting near the boundary creates many immediate escape paths
  • Very small grids such as 1 x 1 cause exits in almost every direction
  • Large move counts create huge numbers, so modulo arithmetic must be applied consistently
  • Revisiting cells must not cause repeated recomputation

Approaches

The most direct approach is to recursively explore every possible sequence of moves.

From each position, we try all four directions:

  • up
  • down
  • left
  • right

If the move leaves the grid, we count one successful path.

If the move remains inside the grid and we still have moves remaining, we continue recursively.

This approach is correct because it explicitly explores every valid path the ball can take.

However, it is extremely inefficient. The recursion tree branches four ways at every move, producing an exponential number of states.

The worst case complexity is:

$O(4^{ ext{maxMove}})$

This becomes completely impractical for maxMove = 50.

The major issue is repeated computation. The same state:

  • current row
  • current column
  • remaining moves

can be reached through many different paths, but the brute force solution recomputes it every time.

Optimal Dynamic Programming

The key insight is that the future result from a state depends only on:

  • the current position
  • the number of remaining moves

If we already know the number of escape paths from (row, col, remainingMoves), we should reuse that result instead of recalculating it.

This leads naturally to dynamic programming with memoization.

For every state:

dp(row, col, movesRemaining)

we compute:

  • 1 if a move exits the grid
  • otherwise the sum of all four recursive directions

Each unique state is solved once and cached.

Since:

  • there are at most 50 * 50 * 50 states
  • each state explores exactly 4 directions

the solution becomes efficient enough.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force $O(4^{ ext{maxMove}})$ $O( ext{maxMove})$ Explores every possible path recursively
Optimal Dynamic Programming Reuses overlapping subproblems with memoization

Algorithm Walkthrough

  1. Define a recursive function dfs(row, col, movesLeft).

This function returns the number of ways the ball can leave the grid starting from (row, col) with movesLeft remaining. 2. Handle the boundary condition first.

If (row, col) is outside the grid, we have successfully exited the boundary, so return 1. 3. Handle the move exhaustion condition.

If movesLeft == 0 and the ball is still inside the grid, no further movement is possible, so return 0. 4. Check whether this state has already been computed.

Since many paths can revisit the same state, memoization avoids repeated work. 5. Explore all four directions.

For each move:

  • up
  • down
  • left
  • right

recursively compute the number of escape paths with one fewer remaining move. 6. Sum all recursive results.

Because the number can grow very large, apply modulo 10^9 + 7 after additions. 7. Store the computed result in the memoization cache.

This ensures future calls for the same state return instantly. 8. Start the recursion from (startRow, startColumn, maxMove).

Why it works

The algorithm works because every valid path can be decomposed into smaller subproblems. From any cell, the total number of escape paths equals the sum of the escape paths from its neighboring cells after one move. Memoization guarantees each state is solved exactly once, while recursion ensures every possible valid path is counted.

Python Solution

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

        memo = {}

        directions = [
            (-1, 0),  # up
            (1, 0),   # down
            (0, -1),  # left
            (0, 1)    # right
        ]

        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

            state = (row, col, moves_left)

            if state in memo:
                return memo[state]

            total_paths = 0

            for dr, dc in directions:
                next_row = row + dr
                next_col = col + dc

                total_paths += dfs(
                    next_row,
                    next_col,
                    moves_left - 1
                )

                total_paths %= MOD

            memo[state] = total_paths

            return total_paths

        return dfs(startRow, startColumn, maxMove)

The implementation begins by defining the modulo constant and the four movement directions.

The memo dictionary stores previously computed states. Each key is a tuple:

(row, col, moves_left)

This uniquely identifies a subproblem.

The recursive dfs function first checks whether the ball has already left the grid. If so, it returns 1 because this path successfully escaped.

If no moves remain and the ball is still inside the grid, the function returns 0.

Before doing any recursive work, the function checks whether the current state has already been computed. If it has, the cached value is returned immediately.

The recursive loop explores all four neighboring positions. Each recursive result is added into total_paths, and modulo arithmetic prevents overflow.

Finally, the result is stored in memo and returned.

Go Solution

func findPaths(m int, n int, maxMove int, startRow int, startColumn int) int {
	const MOD int = 1000000007

	type State struct {
		row   int
		col   int
		moves int
	}

	memo := make(map[State]int)

	directions := [][]int{
		{-1, 0},
		{1, 0},
		{0, -1},
		{0, 1},
	}

	var dfs func(int, int, int) int

	dfs = func(row int, col int, movesLeft int) int {
		if row < 0 || row >= m || col < 0 || col >= n {
			return 1
		}

		if movesLeft == 0 {
			return 0
		}

		state := State{row, col, movesLeft}

		if value, exists := memo[state]; exists {
			return value
		}

		totalPaths := 0

		for _, dir := range directions {
			nextRow := row + dir[0]
			nextCol := col + dir[1]

			totalPaths += dfs(nextRow, nextCol, movesLeft-1)
			totalPaths %= MOD
		}

		memo[state] = totalPaths

		return totalPaths
	}

	return dfs(startRow, startColumn, maxMove)
}

The Go solution follows the same recursive memoized dynamic programming strategy as the Python version.

A custom State struct is used as the memoization key because Go maps require comparable key types.

The recursive function is declared using a function variable so it can recursively reference itself.

Modulo operations are applied after each addition to avoid integer overflow.

Unlike Python, Go does not have built in tuple keys, so the struct serves that purpose cleanly and efficiently.

Worked Examples

Example 1

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

The grid looks like:

(0,0) (0,1)
(1,0) (1,1)

We start at (0,0) with 2 moves.

Step 1

Possible first moves:

Move Result
Up Out of bounds
Left Out of bounds
Down (1,0)
Right (0,1)

Immediate exits contribute:

2 paths

Step 2

From (1,0) with 1 move left:

Move Result
Down Out
Left Out
Up (0,0)
Right (1,1)

This contributes:

2 additional paths

From (0,1) with 1 move left:

Move Result
Up Out
Right Out
Left (0,0)
Down (1,1)

This contributes:

2 additional paths

Total:

2 + 2 + 2 = 6

Final answer:

6

Example 2

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

Grid:

(0,0) (0,1) (0,2)

The ball starts in the center.

First move possibilities

Move Result
Up Out
Down Out
Left (0,0)
Right (0,2)

Immediate exits:

2

Recursive exploration continues from the remaining positions.

Dynamic programming prevents recalculating states like:

(0,0,1)
(0,2,1)

After all recursive states are computed, the total becomes:

12

Complexity Analysis

Measure Complexity Explanation
Time Each state is computed once
Space Memoization stores all unique states

There are at most:

m * n * maxMove

distinct states.

Each state explores exactly four directions, which is constant work.

The recursion depth is at most maxMove, while the memoization table dominates the overall space complexity.

Test Cases

solution = Solution()

# Example 1
assert solution.findPaths(2, 2, 2, 0, 0) == 6

# Example 2
assert solution.findPaths(1, 3, 3, 0, 1) == 12

# No moves allowed
assert solution.findPaths(2, 2, 0, 0, 0) == 0

# Single cell grid, one move
assert solution.findPaths(1, 1, 1, 0, 0) == 4

# Single row grid
assert solution.findPaths(1, 2, 2, 0, 0) == 6

# Starting near edge
assert solution.findPaths(3, 3, 1, 0, 1) == 1

# Starting in center with small moves
assert solution.findPaths(3, 3, 2, 1, 1) == 4

# Larger move count
assert solution.findPaths(2, 3, 8, 1, 0) > 0

# Large constraints stress test
assert solution.findPaths(50, 50, 50, 25, 25) >= 0

# Corner start position
assert solution.findPaths(3, 3, 3, 0, 0) > 0
Test Why
2x2, moves=2 Validates the first provided example
1x3, moves=3 Validates the second provided example
maxMove=0 Ensures no movement returns zero
1x1 grid Every direction immediately exits
1x2 grid Tests narrow boundary behavior
start near edge Verifies immediate boundary exits
start in center Tests internal recursive expansion
larger move count Ensures recursion and memoization scale
50x50 grid Stress tests upper constraints
corner start Tests maximum boundary exposure

Edge Cases

Zero Allowed Moves

If maxMove = 0, the ball cannot move at all. Even if the starting position is adjacent to the boundary, the answer must still be 0 because exiting requires at least one move.

This case is handled directly by:

if moves_left == 0:
    return 0

Single Cell Grid

A 1 x 1 grid is a special scenario because every possible direction immediately leaves the grid.

For example:

m = 1
n = 1
maxMove = 1

All four directions produce successful exits, so the answer is 4.

This can expose bugs in boundary checking if out of bounds detection is implemented incorrectly.

Large Move Counts

With maxMove = 50, the number of possible paths grows extremely quickly.

Without memoization, the recursive solution becomes infeasible.

Additionally, the result can exceed normal integer ranges, which is why modulo arithmetic is applied after every addition:

total_paths %= MOD

This guarantees correctness even for extremely large counts.