LeetCode 576: Out of Boundary Paths Solution in Python – A Step-by-Step Guide

Imagine you’re rolling a ball on a grid—like a 3x3 board starting at position (1,1)—and you need to count how many different ways it can roll off the edge within a limited number of moves, say 2, moving up, down, left, or right each time. That’s the intriguing challenge of LeetCode 576: Out of Boundary Paths, a medium-to-hard problem that’s a fantastic way to practice dynamic programming in Python. We’ll explore two solutions: the Best Solution, a dynamic programming approach with memoization that’s efficient and clever, and an Alternative Solution, a brute-force DFS that’s thorough but less scalable. With detailed examples, clear code, and a friendly tone—especially for the DP method—this guide will help you tally those paths, whether you’re new to coding or leveling up. Let’s roll that ball and start counting!

What Is LeetCode 576: Out of Boundary Paths?

In LeetCode 576: Out of Boundary Paths, you’re given integers m and n defining an m x n grid, an integer maxMove for the maximum number of moves, and starting coordinates startRow and startCol. Your task is to return the number of distinct paths the ball can take to move out of the grid within maxMove moves, modulo 10⁹ + 7, where each move can be up, down, left, or right. For example, with m = 2, n = 2, maxMove = 2, startRow = 0, startCol = 0, the result is 6 (paths out from (0,0)). This problem builds on LeetCode 62: Unique Paths for grid traversal but focuses on exiting boundaries with a move limit.

Problem Statement

Input: m (int)—grid rows; n (int)—grid columns; maxMove (int)—max moves; startRow (int)—start row; startCol (int)—start column.
Output: Integer—number of paths to exit grid within maxMove moves, modulo 10⁹ + 7.
Rules: Move up, down, left, right; count paths exiting grid; result modulo 10⁹ + 7.

Constraints

1 <= m, n <= 50
0 <= maxMove <= 50
0 <= startRow < m
0 <= startCol < n

Examples

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startCol = 0

Output: 6
From (0,0): Out in 1 move (up, left), out in 2 moves (right-up, right-left, down-up, down-left).

Input: m = 1, n = 3, maxMove = 3, startRow = 0, startCol = 1

Output: 12
From (0,1): Multiple paths left/right within 3 moves.

Input: m = 1, n = 1, maxMove = 1, startRow = 0, startCol = 0

Output: 4
Out in 1 move (up, down, left, right).

Understanding the Problem: Counting Boundary Paths

To solve LeetCode 576: Out of Boundary Paths in Python, we need to count all distinct paths a ball can take to exit an m x n grid from a starting position within maxMove moves, considering four possible moves per step, and return the result modulo 10⁹ + 7. With grid sizes up to 50x50 and moves up to 50, a brute-force DFS exploring all paths (O(4^N)) is impractical. Instead, dynamic programming with memoization efficiently computes paths by caching results for each position and move count. We’ll explore:

Best Solution (Dynamic Programming with Memoization): O(m n maxMove) time, O(m n maxMove) space—fast and optimal.
Alternative Solution (Brute-Force DFS): O(4^maxMove) time, O(maxMove) space—simple but slow.

Let’s dive into the DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with Memoization

Why DP Wins

The dynamic programming with memoization solution is the best for LeetCode 576 because it computes the number of paths in O(m * n * maxMove) time and O(m * n * maxMove) space by using a memoized recursive function to count paths from each position and remaining move count, avoiding redundant calculations with a cache. It’s like mapping out every possible roll of the ball, remembering where it’s been to save time—all in a structured, efficient way!

How It Works

Think of this as a path-counting strategist:

Step 1: Define DP State:

dp(moves, row, col): Number of paths to exit from (row, col) with moves left.

Step 2: Base Cases:

Out of moves (moves < 0): 0 paths.
Out of bounds: 1 path (just exited).

Step 3: Recursive Case:

For each direction (up, down, left, right):

Recurse with moves-1, new position.
Sum paths modulo 10⁹ + 7.

Step 4: Memoize:

Cache results using @cache or dictionary.

Step 5: Return Result:

Call dp(maxMove, startRow, startCol).

Why It Works:

Memoization prevents recomputing overlapping subproblems.
Covers all valid paths within move limit.

It’s like a boundary-path tallier!

Step-by-Step Example

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

Init: MOD = 10⁹ + 7.
Step 1: Call dp(2, 0, 0):

Up: (-1,0) → Out, 1 path.
Down: (1,0):

Up: (0,0) → dp(0,0,0) → 0 (no moves).
Down: (2,0) → Out, 1 path.
Left: (1,-1) → Out, 1 path.
Right: (1,1) → dp(0,1,1) → 0.
Total = 2.

Left: (0,-1) → Out, 1 path.
Right: (0,1):

Up: (-1,1) → Out, 1 path.
Down: (1,1) → dp(0,1,1) → 0.
Left: (0,0) → dp(0,0,0) → 0.
Right: (0,2) → Out, 1 path.
Total = 2.

Step 2: Total = 1 + 2 + 1 + 2 = 6.
Result: 6.

Example: m = 1, n = 1, maxMove = 1, startRow = 0, startCol = 0

Step 1: dp(1, 0, 0):

Up: (-1,0) → Out, 1.
Down: (1,0) → Out, 1.
Left: (0,-1) → Out, 1.
Right: (0,1) → Out, 1.

Step 2: Total = 1 + 1 + 1 + 1 = 4.
Result: 4.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

        # Step 1: Memoization with cache decorator
        from functools import cache
        @cache
        def dp(moves: int, row: int, col: int) -> int:
            # Step 2: Base cases
            if moves < 0:
                return 0  # No moves left, no paths
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1  # Out of bounds, 1 path

            # Step 3: Recursive case - try all four directions
            total = 0
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # Up, down, left, right
            for dr, dc in directions:
                total = (total + dp(moves - 1, row + dr, col + dc)) % MOD

            return total

        # Step 4: Return result with initial call
        return dp(maxMove, startRow, startCol)

Line 4: Define modulo constant.
Lines 7-8: Use @cache for memoization.
Lines 10-13: Base cases: no moves (0), out of bounds (1).
Lines 16-19: Recurse on four directions, sum paths modulo 10⁹ + 7.
Line 22: Start recursion from initial position.
Time Complexity: O(m n maxMove)—states in DP table.
Space Complexity: O(m n maxMove)—memoization cache.

It’s like a path-counting maestro!

Alternative Solution: Brute-Force DFS

Why an Alternative Approach?

The brute-force DFS explores all possible move sequences up to maxMove, counting paths that exit the grid, running in O(4^maxMove) time and O(maxMove) space. It’s simple but impractical for large maxMove, making it a good baseline for small inputs or understanding.

How It Works

Picture this as a path-exploring wanderer:

Step 1: Start DFS from (startRow, startCol) with maxMove.
Step 2: Recursively try all four moves, count exits.
Step 3: Sum paths modulo 10⁹ + 7.
Step 4: Return total.

It’s like a boundary-path roamer!

Step-by-Step Example

Example: m = 1, n = 1, maxMove = 1, startRow = 0, startCol = 0

DFS(1, 0, 0):

Up: (-1,0) → Out, 1.
Down: (1,0) → Out, 1.
Left: (0,-1) → Out, 1.
Right: (0,1) → Out, 1.

Total: 4.
Result: 4.

Code for Brute-Force Approach

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

        def dfs(moves: int, row: int, col: int) -> int:
            if row < 0 or row >= m or col < 0 or col >= n:
                return 1
            if moves == 0:
                return 0
            total = 0
            directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
            for dr, dc in directions:
                total = (total + dfs(moves - 1, row + dr, col + dc)) % MOD
            return total

        return dfs(maxMove, startRow, startCol)

Lines 5-14: DFS: Out of bounds (1), no moves (0), recurse on directions.
Line 16: Start DFS.
Time Complexity: O(4^maxMove)—exponential paths.
Space Complexity: O(maxMove)—recursion stack.

It’s a brute-force path counter!

Comparing the Two Solutions

DP (Best):

Pros: O(m n maxMove), O(m n maxMove), fast.
Cons: Memoization space.

DFS (Alternative):

Pros: O(4^maxMove), O(maxMove), simple.
Cons: Exponential time.

DP wins for efficiency!

Additional Examples and Edge Cases

m=1, n=1, maxMove=0: 0.
Large grid: Paths scale with moves.
Edge start: Immediate exits.

DP handles them all!

Complexity Recap

DP: Time O(m n maxMove), Space O(m n maxMove).
DFS: Time O(4^maxMove), Space O(maxMove).

DP’s the speed champ!

Key Takeaways

DP: Path caching—learn at Python Basics!
DFS: Path roam.
Grids: Paths are fun.
Python: DP or DFS, your pick!

Final Thoughts: Count Those Paths!

LeetCode 576: Out of Boundary Paths in Python is a clever DP challenge. Dynamic programming with memoization is your fast track, while brute-force DFS offers a thorough dive. Want more? Try LeetCode 62: Unique Paths or LeetCode 980: Unique Paths III. Ready to roll? Head to Solve LeetCode 576 on LeetCode and tally those boundary paths today!