Out of Boundary Paths

Out of Boundary Paths

What is this problem about?

The Out of Boundary Paths problem asks: given an m×n grid, a ball starting at position (startRow, startCol), and exactly maxMove moves to make, how many distinct paths lead the ball outside the grid? Return the count modulo 10^9+7. This coding problem uses DP counting paths that exit the boundary within a move budget.

Why is this asked in interviews?

Apple, Amazon, and Bloomberg ask this because it requires counting paths in a bounded grid with a step budget, tracking partial paths that leave the boundary. The dynamic programming interview pattern is demonstrated with careful boundary handling.

Algorithmic pattern used

DP with step count. dp[move][row][col] = number of ways to be at (row,col) after exactly move moves. Count paths that exit: whenever a move leads outside the boundary, add to result. Transition: for each in-bounds cell (r,c) at step k, each of 4 directions either exits (adds dp[k][r][c] to result) or leads to in-bounds next cell (adds to dp[k+1][nr][nc]).

Example explanation

m=2, n=2, maxMoves=2, startRow=0, startCol=0.

• Move 1 from (0,0): moves up→out(count+1), left→out(count+1), right→(0,1)in, down→(1,0)in.
• Move 2 from (0,1): moves up→out, right→out, down→(1,1)in, left→(0,0)in.
• Move 2 from (1,0): similar. Total paths leaving boundary in ≤2 moves = 6.

Common mistakes candidates make

• Counting paths that exit and re-enter (must count paths that exit at any step and stop).
• Not applying modular arithmetic.
• Incorrect bounds check (< 0 or ≥ m/n means out of boundary).
• Using recursion without memoization (exponential recomputation).

Interview preparation tip

Grid DP problems with "count paths reaching/exiting boundary" work backwards from the boundary condition. The key: when a step leads outside the grid, add the current state's count to the result rather than continuing the DP. Rolling array space optimization reduces from O(maxMove * m * n) to O(2 * m * n). Practice similar "count paths in bounded grid with limited budget" problems — they appear frequently at Apple and Bloomberg.