Skip to main content

576. Out of Boundary Paths

medium

Count the number of N-move paths that take a ball off an m x n grid starting from a given cell. Counting DP over (position, moves-left) — exactly the kind of state-space expansion that converts a 2D grid into a 3D recurrence.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

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 grid crossing the grid boundary). You can apply at most maxMove moves to the ball. Given the five integers m, n, maxMove, startRow, 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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

State: (row, col, movesLeft). Transitions are the four neighbors with movesLeft - 1.

Hint 2

Base case: if (row, col) is out of bounds, you've succeeded — return 1.

Hint 3

If movesLeft == 0 and you're still in bounds, return 0.

Hint 4

Memoize (row, col, movesLeft). Apply mod 10^9 + 7 after every addition.

Solution approach

Reveal approach

Top-down memoization on (row, col, movesLeft). If the cell is outside the grid, return 1 (a successful exit). If movesLeft == 0, return 0. Otherwise return the sum of dp(row +/- 1, col, movesLeft - 1) and dp(row, col +/- 1, movesLeft - 1), modulo 10^9 + 7. Bottom-up version maintains two m x n boards: one for the current move count, one for the previous. For each move count from 1 to maxMove, each cell's value is the sum of its four neighbors' values from the previous count — out-of-bounds neighbors contribute 1. The answer is the cell (startRow, startColumn) after maxMove iterations.

Complexity

Time
O(maxMove * m * n)
Space
O(maxMove * m * n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Bloomberg

Practice these live with InterviewChamp.AI

Drill Out of Boundary Paths and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →