576 - Out of Boundary Paths

Difficulty: Medium | Pattern: Dynamic Programming (3D) | Company tags: Amazon, Google

Problem Statement

There is an m x n grid with a ball. The ball is initially at the position [startRow, startColumn]. You are allowed to move the ball to one of the four adjacent cells in the grid (possibly out of the boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, and startColumn, return the number of paths to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

Example 1:

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

Example 2:

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

Approach: DP — O(maxMove × m × n)

Key insight: dp[k][r][c] = number of paths using exactly k moves from (r,c) that exit the grid. Build bottom-up from k=1 to k=maxMove.

def findPaths(m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
    MOD = 10**9 + 7
    dp = [[0] * n for _ in range(m)]
    dp[startRow][startColumn] = 1
    result = 0
    
    for k in range(maxMove):
        new_dp = [[0] * n for _ in range(m)]
        for r in range(m):
            for c in range(n):
                if dp[r][c] == 0:
                    continue
                for dr, dc in [(-1,0),(1,0),(0,-1),(0,1)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < m and 0 <= nc < n:
                        new_dp[nr][nc] = (new_dp[nr][nc] + dp[r][c]) % MOD
                    else:
                        result = (result + dp[r][c]) % MOD
        dp = new_dp
    
    return result

Algorithm Flow

Dry Run

m=2, n=2, maxMove=2, start=(0,0)

k=1: From (0,0) — two moves exit (left=out, up=out), two go to (0,1) and (1,0) result=2, dp: (0,1)→1, (1,0)→1

k=2: From (0,1) — right=out, up=out → result += 2; also (0,0), (1,1) From (1,0) — left=out, down=out → result += 2; also (0,0), (1,1) Total result = 2+2+2 = 6 ✓

Complexity

• Time: O(maxMove × m × n)
• Space: O(m × n) — rolling two layers

Key Terms

Term	Definition
DP state (k, r, c)	Number of ways the ball can move from cell (r, c) using exactly k remaining moves and exit the grid.
Transition	From (r, c) at move k, the ball moves to one of 4 neighbors; each in-bounds move carries the count forward, each out-of-bounds move contributes to the answer.
Rolling array	Since dp[k] only depends on dp[k-1], only two m x n layers are needed instead of a full maxMove x m x n table.
Modulo arithmetic	Counts are taken % (10^9 + 7) after every addition to prevent integer overflow on large maxMove.
Boundary check	0 <= nr < m and 0 <= nc < n distinguishes an in-grid move (continue counting) from an exit (add to result).

FAQ

Q1: Why iterate moves outermost instead of rows/columns? Because dp[k] depends only on the complete dp[k-1] layer (every cell must have finished being updated for move k-1 before move k starts). Iterating moves outermost enforces this ordering naturally.

Q2: Can this be solved with plain memoized recursion instead of bottom-up DP? Yes — paths(r, c, k) recursing on remaining moves, memoized on (r, c, k), gives the same complexity. Bottom-up avoids recursion overhead and stack depth issues for large maxMove.

Q3: Why do we need modulo here, and does it change the algorithm's correctness? The number of paths grows roughly as 4^maxMove, which overflows fixed-size integers in most languages. Taking % (10^9+7) at each accumulation keeps values bounded without affecting the final answer's correctness (mod arithmetic distributes over addition).

Q4: What's the time/space complexity trade-off if maxMove is very large but m, n are small? Time stays O(maxMove * m * n), which is linear in maxMove — no way to avoid touching every move step with this DP. For extremely large maxMove, matrix exponentiation on the transition matrix could reduce this to O(m*n)^3 * log(maxMove), though that's rarely required in interviews.

Q5: How is this different from Unique Paths (LeetCode 62)? Unique Paths counts paths within a fixed grid from a corner to a corner with a fixed number of moves determined by grid size. This problem instead counts paths that leave the grid within a move budget, starting from an arbitrary interior cell — the DP transition direction (accumulating exits vs. accumulating arrivals) is reversed.

Quick Revision

• Problem: count paths (mod 1e9+7) for a ball starting at (startRow, startColumn) to exit an m x n grid using at most maxMove moves.
• State: dp[r][c] = ways to exit from (r, c) with the moves remaining at the current step.
• Transition: for each of 4 neighbors, if in bounds add to next layer; if out of bounds add to result.
• Iterate k from 1 to maxMove, refreshing a new dp grid each iteration (rolling array).
• Base case: dp[startRow][startColumn] = 1 before any moves are used.
• Every move consumed reduces the remaining budget by 1 — moves are irreversible, ball never gets "extra" moves back.
• Time: O(maxMove * m * n); Space: O(m * n).
• Answer accumulates across all k values from 1 to maxMove, not just the last layer.
• Sanity check: m=1, n=1 gives result = 4 for any maxMove >= 1 — all 4 first-move directions exit immediately, and dp becomes all zeros afterward so later moves add nothing.

Related Problems

• 62 - UniquePaths — counts paths in a fixed grid without exiting, same 2D grid-DP transition style.
• 63 - UniquePathsII — grid-DP variant with obstacles blocking transitions.
• 1197 - MinimumKnightMoves — another bounded-move grid state-space problem, using BFS instead of DP over a move budget.