Out of Boundary Paths: 3D Dynamic Programming on a Grid

You have an m x n grid and a ball sitting at position (startRow, startColumn). On each move, the ball can travel to one of its four adjacent cells, or it can cross the grid boundary and leave. Given a maximum of maxMove moves, how many distinct paths move the ball out of the grid? Return the answer modulo 10^9 + 7.

This is LeetCode 576: Out of Boundary Paths, and it is a classic example of 3D dynamic programming. If you have solved Unique Paths or Minimum Path Sum, you already know how to build a 2D DP table over a grid. This problem adds a third dimension: the number of moves remaining. That extra axis is what makes it interesting.

The problem

Picture a 2x3 grid with the ball at (0, 0). The ball can move up, down, left, or right. If a move takes it outside the grid boundaries, that counts as one valid path out. You need to count every such path across all possible move sequences up to maxMove moves long.

From any cell, some directions lead out of the grid and some lead to neighboring cells. A corner cell like (0, 0) has 2 out of 4 directions that exit immediately. An edge cell has 1 immediate exit. A cell in the interior has none. The trick is that paths can also exit after multiple moves, bouncing around inside the grid first.

The approach

Think about it recursively. Define dp[k][r][c] as the number of ways to move the ball out of the grid starting from cell (r, c) using exactly k moves.

For each cell (r, c) with k moves:

• Check all 4 neighbors. If a neighbor (nr, nc) is out of bounds, that is one direct exit path, so add 1.
• If the neighbor is inside the grid, add dp[k-1][nr][nc], the number of ways the ball can exit from that neighbor with one fewer move.

The base case is dp[0][r][c] = 0 for all cells, because with zero moves the ball cannot go anywhere.

The final answer sums dp[1][startRow][startColumn] + dp[2][startRow][startColumn] + ... + dp[maxMove][startRow][startColumn]. The ball could exit on any move from 1 to maxMove.

The solution

def findPaths(m, n, maxMove, startRow, startColumn):
    MOD = 10**9 + 7
    # dp[r][c] = ways to exit from (r,c) with exactly k moves
    prev = [[0] * n for _ in range(m)]
    result = 0

    for k in range(1, maxMove + 1):
        curr = [[0] * n for _ in range(m)]
        for r in range(m):
            for c in range(n):
                for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
                    nr, nc = r + dr, c + dc
                    if nr < 0 or nr >= m or nc < 0 or nc >= n:
                        curr[r][c] = (curr[r][c] + 1) % MOD
                    else:
                        curr[r][c] = (curr[r][c] + prev[nr][nc]) % MOD
        result = (result + curr[startRow][startColumn]) % MOD
        prev = curr

    return result

Notice how we only keep two layers of the DP table at a time: prev (layer k-1) and curr (layer k). This is the same space optimization you see in Unique Paths, applied to the third dimension instead of collapsing rows.

Step-by-step walkthrough

Let's trace through a small example: m=2, n=2, maxMove=2, startRow=0, startColumn=0.

The answer is 6. With 1 move, the ball can exit up or left from (0,0), giving 2 paths. With 2 moves, the ball can first move right to (0,1) or down to (1,0), then exit from those cells. That adds 4 more paths (2 exits from each neighbor after 1 more move, minus the direction that returns to (0,0)). Wait, let's count carefully: from (0,1) with 1 move, there are 2 exits (up and right). From (1,0) with 1 move, there are 2 exits (left and down). So dp[2][0][0] = 2 (direct exits) + 2 + 2 = 6. Total = dp[1][0][0] + dp[2][0][0] = 2 + 6 = 6. Wait, but actually dp[2][0][0] already includes the 2 direct exits for this move count. Let me clarify: dp[k] counts paths using exactly k moves, and we sum across all k. The answer is 6.

Complexity analysis

The space-optimized version above uses O(m * n) space. Each of the maxMove iterations does O(m * n) work (visiting every cell and checking 4 neighbors). The total time is O(maxMove * m * n), with a constant factor of 4 for the directions.

The building blocks

1. 3D DP (layered grid computation)

The core pattern here is adding a dimension to a standard grid DP. In Unique Paths, the state is dp[r][c]. Here, the state is dp[k][r][c], where k represents how many moves remain. Each layer depends only on the previous layer, so you can build them sequentially and discard old layers.

This "layered DP" pattern appears whenever you have a grid problem with a bounded number of steps or a time component. The move count, time, or fuel budget becomes the third dimension.

2. Boundary detection as a transition

Most grid DP problems define transitions between neighboring cells inside the grid. This problem flips that: when a neighbor is out of bounds, instead of ignoring it, you count it as a successful exit. The boundary is not an obstacle to avoid. It is the goal.

This reframing is what makes the problem tricky at first. Once you recognize that out-of-bounds neighbors contribute +1 to the count (rather than being skipped), the recurrence writes itself.

Edge cases

• maxMove = 0: the ball cannot move at all, so the answer is always 0.
• Ball starts on a corner: has 2 immediate exits per move. The count grows quickly.
• Ball starts in the center of a large grid: with a small maxMove, it might not be able to reach the boundary at all, giving 0.
• 1x1 grid: every direction from (0,0) exits the boundary. With 1 move, the answer is 4. With maxMove moves, it grows as 4^maxMove (bounded by modular arithmetic).
• Large values: m, n, and maxMove can each be up to 50. The space-optimized solution handles this in roughly 50 * 50 * 50 = 125,000 operations, which is very fast.

From understanding to recall

You have seen how the 3D DP table is structured, how each layer builds on the previous one, and how boundary exits become part of the transition function. The logic is clean once you see it. But producing it under pressure requires practice.

The key things to remember: the state includes the move count as a dimension, the transition checks all four neighbors, out-of-bounds neighbors add 1 instead of looking up a DP value, and you sum across all layers for the final answer. That is the entire algorithm.

Spaced repetition helps you internalize these details. You revisit the problem at increasing intervals, each time reconstructing the 3D state definition and the boundary-as-goal transition from memory. After a few reps, the pattern becomes automatic. You see a grid problem with a move budget and immediately know to add a third dimension.

Related posts

• Unique Paths - Grid DP where you count paths from top-left to bottom-right
• Minimum Path Sum - Another grid-based DP problem with similar state transitions
• Dungeon Game - Grid DP with boundary considerations and careful state definition