#576

Medium

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Out of Boundary Paths

Calculate the number of ways a ball can exit a grid using dynamic programming with state transitions for every move combination.

dynamic programming

Problem Statement

You are given an m x n grid with a ball positioned at [startRow, startColumn]. You can move the ball to any of the four adjacent cells (up, down, left, right) for at most maxMove moves. A move that sends the ball outside the grid counts as exiting the boundary. Return the total number of paths that move the ball out of the grid.

Since the number of paths can be very large, return the result modulo 10^9 + 7. For example, given m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0, the number of paths that exit the boundary is 6.

Examples

Example 1

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

Output: 6

Example details omitted.

Example 2

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

Output: 12

Example details omitted.

Constraints

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

Solution Approach

Top-Down Recursive DP with Memoization

Define a recursive function dp(r, c, movesLeft) that returns the number of boundary-exiting paths from cell (r, c) with movesLeft remaining. If the ball is out of bounds, return 1. If movesLeft is 0, return 0. Use a 3D memoization table to store results for each state to avoid recomputation.

Bottom-Up Iterative DP

Create a 3D DP array where dp[moves][r][c] represents the number of paths to exit from cell (r, c) using exactly 'moves' moves. Initialize paths for 0 moves to 0 and iteratively compute the counts for moves from 1 to maxMove by summing results from four neighboring cells, adding 1 when moving out of bounds.

Space Optimization

Since only the previous move state is required to compute the next, maintain two 2D arrays and alternate updates to reduce space from O(m n maxMove) to O(m n 2). This retains correctness while improving memory efficiency for large grids and move limits.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(maxMove * m * n) because each move updates all grid positions. Space complexity can be O(m * n * maxMove) for full DP or optimized to O(m * n) using rolling arrays.

What Interviewers Usually Probe

Consider whether traversing every possible path recursively is feasible for larger maxMove values.
Expect hints towards state transition DP and memoization to handle repeated subproblems efficiently.
Watch for discussions on space optimization or iterative DP to improve performance for grids up to 50x50.

Common Pitfalls or Variants

Common pitfalls

Failing to correctly count paths when the ball moves out of bounds immediately.
Recomputing subproblems without memoization, causing exponential runtime.
Ignoring modulo 10^9 + 7, which can cause integer overflow in large grids or many moves.

Follow-up variants

Compute paths when diagonal moves are also allowed, requiring adjustments to the DP state transitions.
Modify the problem to count paths of exactly maxMove moves instead of up to maxMove.
Return all unique sequences of moves leading out of the grid instead of just counts, which increases combinatorial complexity.

FAQ

What pattern does Out of Boundary Paths primarily use?

This problem is a classic state transition dynamic programming scenario where each cell's exit paths depend on adjacent cells and remaining moves.

Can I solve this problem with brute force recursion?

Brute force is impractical for large grids or maxMove because the number of possible paths grows exponentially, causing timeouts.

How do I handle large outputs in this problem?

Use modulo 10^9 + 7 arithmetic at each step to prevent integer overflow while computing path counts.

Is iterative DP better than recursive DP here?

Iterative DP is often preferred for clarity and avoids stack overflow, while recursive DP with memoization is easier to write but may need extra care for large maxMove values.

How can I reduce space usage for this problem?

Maintain only two 2D arrays for the current and previous move states to reduce space from O(m n maxMove) to O(m*n) without affecting correctness.

terminal

Solution

Solution 1: Memoization Search

We define a function $\textit{dfs}(i, j, k)$ to represent the number of paths that can move out of the boundary starting from coordinates $(i, j)$ with $k$ steps remaining.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def findPaths(
        self, m: int, n: int, maxMove: int, startRow: int, startColumn: int
    ) -> int:
        @cache
        def dfs(i: int, j: int, k: int) -> int:
            if not 0 <= i < m or not 0 <= j < n:
                return int(k >= 0)
            if k <= 0:
                return 0
            ans = 0
            for a, b in pairwise(dirs):
                x, y = i + a, j + b
                ans = (ans + dfs(x, y, k - 1)) % mod
            return ans

        mod = 10**9 + 7
        dirs = (-1, 0, 1, 0, -1)
        return dfs(startRow, startColumn, maxMove)

Continue Practicing

#583 delete operation for two strings #553 optimal division #552 student attendance record ii