Out of Boundary Paths — Solution in Python, Java & C++
Out of Boundary Paths solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Out of Boundary Paths is a medium coding problem on dynamic programming and matrix, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Medium
- Topics: Dynamic Programming, Matrix
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A token sits on cell (startRow, startColumn) of an m x n grid. In one move it steps to one of the four orthogonally adjacent cells — and that step may carry it off the grid.
You may make at most maxMove moves. Count the distinct move sequences that end with the token leaving the grid (a sequence stops the moment the token crosses the boundary). Two sequences differ if they differ in any move.
The count can be huge, so return it modulo 10^9 + 7.
Example 1
Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6
Explanation: Two one-move exits (up, left), then from each of the two neighbours two more exits each.
Example 2
Input: m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
Output: 12
Example 3
Input: m = 3, n = 3, maxMove = 1, startRow = 1, startColumn = 1
Output: 0
Explanation: The centre cell is two steps from every edge.
Constraints
1 <= m, n <= 500 <= maxMove <= 500 <= startRow < m0 <= startColumn < n
Hints for Out of Boundary Paths
Hint 1
Only the token's cell and the number of moves used matter — not the path that brought it there.
Hint 2
Track, after each move, how many sequences put the token on each cell.
Hint 3
Spread each cell's count to its four neighbours; whatever lands outside the grid is added to the answer.
How to solve Out of Boundary Paths
Push counts forward one move at a time. ways[r][c] after step t is how many length-t move sequences end on (r, c) without having left; every neighbour that falls outside the grid turns those sequences into finished exits.
Approach
- Start with
ways[startRow][startColumn] = 1and an answer of 0. - Repeat
maxMovetimes: build a fresh zero grid; for every cell with a non-zero count, look at its four neighbours. - A neighbour inside the grid receives the count; a neighbour outside adds the count to the answer. Reduce everything modulo
10^9 + 7. - Replace the grid with the fresh one and continue; return the answer.
Why it works
A sequence that leaves on move t is exactly a sequence of t - 1 in-grid moves followed by one step across the edge, so summing, for each step, the counts that cross the edge counts every exiting sequence once — sequences stop at the edge, so nothing is double counted.
Complexity
- Time —
O(maxMove · m · n) - Space —
O(m · n)
Pitfalls
maxMove = 0must return 0, not 1.- A corner cell has two exits in one move, a cell on a 1-wide grid can have three or four — count each exit separately.
- Reduce after every addition; the raw counts grow like 4^maxMove.
Reference solution
Python
def findPaths(m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
MOD = 10**9 + 7
cur = [[0] * n for _ in range(m)]
cur[startRow][startColumn] = 1
total = 0
for _ in range(maxMove):
nxt = [[0] * n for _ in range(m)]
for r in range(m):
for c in range(n):
w = cur[r][c]
if w == 0:
continue
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < m and 0 <= nc < n:
nxt[nr][nc] = (nxt[nr][nc] + w) % MOD
else:
total = (total + w) % MOD
cur = nxt
return totalJava
public static int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
final int MOD = 1000000007;
int[] dr = {1, -1, 0, 0};
int[] dc = {0, 0, 1, -1};
int[][] cur = new int[m][n];
cur[startRow][startColumn] = 1;
int total = 0;
for (int step = 0; step < maxMove; step++) {
int[][] nxt = new int[m][n];
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int w = cur[r][c];
if (w == 0) continue;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) total = (total + w) % MOD;
else nxt[nr][nc] = (nxt[nr][nc] + w) % MOD;
}
}
}
cur = nxt;
}
return total;
}C++
int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
const int MOD = 1000000007;
int dr[4] = {1, -1, 0, 0};
int dc[4] = {0, 0, 1, -1};
vector<vector<int>> cur(m, vector<int>(n, 0));
cur[startRow][startColumn] = 1;
int total = 0;
for (int step = 0; step < maxMove; step++) {
vector<vector<int>> nxt(m, vector<int>(n, 0));
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
int w = cur[r][c];
if (w == 0) continue;
for (int d = 0; d < 4; d++) {
int nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) total = (total + w) % MOD;
else nxt[nr][nc] = (nxt[nr][nc] + w) % MOD;
}
}
}
cur = nxt;
}
return total;
}JavaScript
var findPaths = function(m, n, maxMove, startRow, startColumn) {
var MOD = 1000000007;
var dr = [1, -1, 0, 0], dc = [0, 0, 1, -1];
var makeGrid = function() {
var g = [];
for (var i = 0; i < m; i++) g.push(new Array(n).fill(0));
return g;
};
var cur = makeGrid();
cur[startRow][startColumn] = 1;
var total = 0;
for (var step = 0; step < maxMove; step++) {
var nxt = makeGrid();
for (var r = 0; r < m; r++) {
for (var c = 0; c < n; c++) {
var w = cur[r][c];
if (w === 0) continue;
for (var d = 0; d < 4; d++) {
var nr = r + dr[d], nc = c + dc[d];
if (nr < 0 || nr >= m || nc < 0 || nc >= n) total = (total + w) % MOD;
else nxt[nr][nc] = (nxt[nr][nc] + w) % MOD;
}
}
}
cur = nxt;
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 402 dynamic programming problems · the whole catalogue
Learn the technique: Dynamic Programming · Matrix and Grid Traversal