Out of Boundary Paths - Practice Coding Problems

Out of Boundary Paths - Problem

Dynamic Programming Medium

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⁹ + 7.

Input & Output

Example 1 — Small Grid

$ Input: m = 2, n = 3, maxMove = 2, startRow = 1, startColumn = 1

› Output: 6

💡 Note: From center position (1,1), the ball can exit the boundary in 6 different ways within 2 moves: moving up-up, up-left, up-right, down-down, down-left, down-right

Example 2 — Single Move

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

› Output: 12

💡 Note: From middle of 1x3 grid, ball can exit left or right in 1 move (2 ways), or make more complex paths using all 3 moves for total of 12 paths

Example 3 — No Moves

$ Input: m = 2, n = 2, maxMove = 0, startRow = 0, startColumn = 0

› Output: 0

💡 Note: With 0 moves allowed, the ball cannot move at all, so there are 0 paths to exit the boundary

Constraints

1 ≤ m, n ≤ 50
0 ≤ maxMove ≤ 50
0 ≤ startRow < m
0 ≤ startColumn < n

Visualization

Tap to expand

Understanding the Visualization

Input

2×3 grid, start at (1,1), max 2 moves

Process

Try all 4 directions, count boundary exits

Output

Total of 6 different paths to exit

Key Takeaway

🎯 Key Insight: Use DP to systematically count all possible boundary-crossing paths

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to use dynamic programming to count paths systematically. Best approach is 2D DP processing each move level iteratively. Time: O(m×n×maxMove), Space: O(m×n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoized Recursion	O(m × n × maxMove)	O(m × n × maxMove)	Cache results to avoid repeated calculations
Recursive Brute Force	O(4^maxMove)	O(maxMove)	Try all possible move sequences recursively
2D Dynamic Programming	O(m × n × maxMove)	O(m × n)	Bottom-up DP with 2D table for each move level

Memoized Recursion — Algorithm Steps

Create memoization cache
Check cache before recursion
Store results in cache
Return cached or computed result

Visualization

Tap to expand

Step-by-Step Walkthrough

First Call

Calculate and store result in cache

Repeated State

Return cached result immediately

Efficient Solution

Each state computed only once

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

const int MOD = 1000000007;
int memo[51][51][51];
int initialized = 0;

void initMemo() {
    if (!initialized) {
        memset(memo, -1, sizeof(memo));
        initialized = 1;
    }
}

int dfs(int m, int n, int x, int y, int moves) {
    if (x < 0 || x >= m || y < 0 || y >= n) {
        return 1;
    }
    if (moves == 0) {
        return 0;
    }
    
    if (memo[x][y][moves] != -1) {
        return memo[x][y][moves];
    }
    
    long long result = 0;
    int directions[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
    for (int i = 0; i < 4; i++) {
        result = (result + dfs(m, n, x + directions[i][0], y + directions[i][1], moves - 1)) % MOD;
    }
    
    memo[x][y][moves] = (int) result;
    return (int) result;
}

int solution(int m, int n, int maxMove, int startRow, int startColumn) {
    initMemo();
    return dfs(m, n, startRow, startColumn, maxMove);
}

int main() {
    int m, n, maxMove, startRow, startColumn;
    scanf("%d", &m);
    scanf("%d", &n);
    scanf("%d", &maxMove);
    scanf("%d", &startRow);
    scanf("%d", &startColumn);
    
    int result = solution(m, n, maxMove, startRow, startColumn);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m × n × maxMove)

Each state (x,y,moves) computed once, m×n×maxMove total states

✓ Linear Growth

Space Complexity

O(m × n × maxMove)

Memoization cache stores result for each state plus recursion stack

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoized Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler