576. Out of Boundary Paths

Problem Description

The problem describes a scenario where a ball is placed on a grid that is m by n in size, and the ball is initially positioned at the grid cell [startRow, startColumn]. The goal is to determine the number of distinct paths that can move the ball out of the grid boundaries, with the constraint that the ball can only be moved a maximum of maxMove times. At each move, the ball can only go to one of the four adjacent cells - up, down, left, or right - and it might move off the grid.

The problem asks for the total number of such paths where the ball exits the grid, constrained by the number of moves allowed, and because the resulting number can be very large, it is necessary to return this number modulo 10^9 + 7.

Intuition

The intuition behind solving this problem lies in using Depth-First Search (DFS) to explore all possible paths from the start position until the ball moves out of the grid or until we have made maxMove moves. To find all paths efficiently, we can use dynamic programming (specifically memoization) to store the results of sub-problems we've already solved. This will avoid redundant computations for the same position and number of moves left, which otherwise would significantly increase the run-time complexity. Specifically, we can apply memoization to remember the number of paths from a given position (i, j) with k moves remaining that lead to the ball exiting the grid.

The recursive function dfs(i, j, k) will return the number of pathways that lead out of the grid starting from cell (i, j) with k moves left. If the ball's current position is already outside the grid, the function returns 1 as it indicates a valid exit path. If no moves are left (k <= 0), the function returns 0 since the ball cannot move further. For each position (i, j) within the grid and with moves remaining, the function explores all four adjacent cells, cumulatively adding up the number of exit paths from those cells to the current count. To keep the count within the specified modulo constraint, the result is taken modulo 10^9 + 7 after each addition.

By starting the recursion with dfs(startRow, startColumn, maxMove), we kick off this exploration process and allow the recursive function to calculate the total number of exit paths from our start position, adhering to the move limit and memoizing along the way to ensure efficiency.

Learn more about Dynamic Programming patterns.

Solution Approach

The implementation of the solution takes a recursive approach with dynamic programming - specifically, it uses memoization to optimize the depth-first search (DFS) algorithm.

Here's a step-by-step explanation of how this is done:

A recursive helper function, dfs(i, j, k), takes parameters i and j representing the current cell's row and column indices, and k representing the number of remaining moves.
The base case of the recursion checks if the current cell is out of bounds - that is, if i, j, k indicates a position outside the grid. If it is out of bounds, we have a complete path, so it returns 1.
If k is 0, meaning no more moves are left, it returns 0 since the ball cannot move out of the grid with no moves remaining.
To avoid repeating calculations for the same positions and move counts, the @cache decorator is used, which stores the results of the dfs calls and returns the cached value when the same arguments are encountered again.
The function then initializes res as 0 to accumulate the number of paths going out of the grid from the current position.
For each allowed move (up, down, left, right), represented by a, b in directions [[-1, 0], [1, 0], [0, 1], [0, -1]], the new cell coordinates x, y are calculated by adding a, b to i, j.
It then recursively calls dfs(x, y, k - 1) to account for moving to the new cell with one less remaining move, and adds this to the res while ensuring to apply the modulo operation % mod to keep the number under 10^9 + 7.
Finally, after going through all possible adjacent moves, the function returns res, the total number of paths from the current cell leading out of the grid.

By calling dfs(startRow, startColumn, maxMove), we start the recursive search from the initial ball position with the maximum allowed moves. The returned result is the total number of paths modulo 10^9 + 7. The algorithm ensures efficiency by avoiding recomputation and considers all possible move sequences leading to an exit path.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's use a small example to illustrate the solution approach. Suppose we have a grid that is 3x3 in size (m = 3, n = 3), and the ball is initially placed at the center grid cell [1, 1]. We want to find the number of distinct paths that can move the ball out of the grid if it can only be moved a maximum of 2 times (maxMove = 2).

The grid can be visualized as:

+---+---+---+
|   |   |   |
+---+---+---+
|   | S |   |
+---+---+---+
|   |   |   |
+---+---+---+

Where 'S' represents the start position of the ball.

We begin by calling the recursive helper function dfs(1, 1, 2).
Since [1, 1] is within the grid bounds and we have more than 0 moves, the recursive function continues.
We check all four possible directions the ball can move: up, down, left, and right.
- Moving up: Call dfs(0, 1, 1) → moves the ball one cell up. Since we can still move 1 more time and the current position is within bounds, recursion continues.
  - From here, dfs(-1, 1, 0) → moves the ball one cell up and out of grid (valid path).
  - Other directions for this step would keep the ball in bounds (so no additional paths added).
- Moving down: Call dfs(2, 1, 1) → moves the ball one cell down. The ball is still in bounds so recursion continues.
  - From here, dfs(3, 1, 0) → moves the ball one cell down and out of grid (valid path).
  - Other directions for this step would keep the ball in bounds (so no additional paths added).
- Moving left: Call dfs(1, 0, 1) → moves the ball one cell to the left. The ball is still in bounds so recursion continues.
  - From here, dfs(1, -1, 0) → moves the ball one cell to the left and out of grid (valid path).
- Moving right: Call dfs(1, 2, 1) → moves the ball one cell to the right. The ball is still in bounds so recursion continues.
  - From here, dfs(1, 3, 0) → moves the ball one cell to the right and out of grid (valid path).
Each time the ball moves out of grid, we return 1 and add that to our total res.
After exploring all possible first moves and the ensuing second move from [1, 1] with 2 moves allowed, res will accumulate the total paths leading out of the grid. Here, we find that there are a total of 4 paths (one for each direction).
Finally, since we do not exceed the modulo 10^9 + 7 with such small numbers, res equals 4. So, dfs(1, 1, 2) returns 4.

By following the steps described in the solution approach and utilizing memoization, we efficiently calculate the total number of distinct paths out of the grid using a recursive DFS algorithm. This approach can be extended to larger grids and more moves as required by the problem.

Solution Implementation

1from functools import lru_cache
2
3class Solution:
4    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
5        # Using the Least Recently Used (LRU) cache decorator for memoization to optimize the solution
6        @lru_cache(maxsize=None)
7        def dfs(row, col, remaining_moves):
8            # Base case: if the current cell (row,col) is out of bounds, return 1 since we've found a way out
9            if row < 0 or col < 0 or row >= m or col >= n:
10                return 1
11            # If no moves left, return 0 since we cannot move further
12            if remaining_moves <= 0:
13                return 0
14          
15            # Accumulate paths' counts from the current cell
16            paths_count = 0
17            # Possible movement directions: up, down, right, left
18            directions = [(-1, 0), (1, 0), (0, 1), (0, -1)]
19            for direction in directions:
20                # Define the new cell to be explored
21                new_row, new_col = row + direction[0], col + direction[1]
22                # Recursive call for the next move
23                paths_count += dfs(new_row, new_col, remaining_moves - 1)
24                # Modulo operation for the final result to prevent integer overflow
25                paths_count %= MOD
26          
27            return paths_count
28      
29        # Modulo constant for the problem
30        MOD = 10**9 + 7
31        # Initial call to depth-first search
32        return dfs(startRow, startColumn, maxMove)
33

1class Solution {
2    private int rowCount; // Total number of rows in the grid
3    private int colCount; // Total number of columns in the grid
4    private int[][][] memoization; // Memoization array to store results of sub-problems
5    private static final int[] DIRECTIONS = {-1, 0, 1, 0, -1}; // Direction array to facilitate movement to adjacent cells
6    private static final int MOD = (int) 1e9 + 7; // Modulus value for the result to prevent overflow
7
8    // Function to calculate the number of paths to move the ball out of the grid boundary
9    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
10        rowCount = m;
11        colCount = n;
12        // Initialize the memoization array with -1 to indicate uncomputed states
13        memoization = new int[rowCount][colCount][maxMove + 1];
14        for (int[][] grid : memoization) {
15            for (int[] row : grid) {
16                Arrays.fill(row, -1);
17            }
18        }
19        // Run DFS from the starting cell
20        return dfs(startRow, startColumn, maxMove);
21    }
22
23    // Helper function using DFS to find paths, with memoization to optimize overlapping subproblems
24    private int dfs(int row, int col, int remainingMoves) {
25        // Base case: if the current position is out of the grid, return 1
26        if (row < 0 || row >= rowCount || col < 0 || col >= colCount) {
27            return 1;
28        }
29        // Check if the current state is already computed
30        if (memoization[row][col][remainingMoves] != -1) {
31            return memoization[row][col][remainingMoves];
32        }
33        // Base case: if no moves left, return 0 as we can't move further
34        if (remainingMoves == 0) {
35            return 0;
36        }
37        // Variable to hold the result
38        int pathCount = 0;
39        // Iterate through all possible directions and explore further moves
40        for (int index = 0; index < 4; ++index) {
41            int nextRow = row + DIRECTIONS[index];
42            int nextCol = col + DIRECTIONS[index + 1];
43            // Recur for the next state with one less move
44            pathCount += dfs(nextRow, nextCol, remainingMoves - 1);
45            // Apply modulo operation to prevent overflow
46            pathCount %= MOD;
47        }
48        // Store the computed result in the memoization array
49        memoization[row][col][remainingMoves] = pathCount;
50        // Return the total number of paths for the current state
51        return pathCount;
52    }
53}
54

1class Solution {
2public:
3    int maxRowCount;
4    int maxColCount;
5    const int MOD = 1e9 + 7; // A constant to take modulo after additions.
6    int memo[51][51][51]; // Memoization table to store intermediate results.
7    int directions[5] = {-1, 0, 1, 0, -1}; // Directions array to perform DFS.
8
9    // Public method to find the number of possible paths which move out of boundary
10    int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
11        memset(memo, -1, sizeof(memo)); // Initialize memoization table with -1.
12        this->maxRowCount = m; // Initialize number of rows in the grid.
13        this->maxColCount = n; // Initialize number of columns in the grid.
14        return dfs(startRow, startColumn, maxMove);
15    }
16
17    // Private helper method for performing DFS traversal.
18    int dfs(int row, int col, int remainingMoves) {
19        // Base condition: if out of boundary, return 1 as one path is found.
20        if (row < 0 || row >= maxRowCount || col < 0 || col >= maxColCount) return 1;
21
22        // Return cached result if already computed.
23        if (memo[row][col][remainingMoves] != -1) return memo[row][col][remainingMoves];
24      
25        // Base condition: if no more moves left, return 0 as no path can be made.
26        if (remainingMoves == 0) return 0;
27
28        // Variable to store the result of paths from the current cell.
29        int pathCount = 0;
30      
31        // Explore all adjacent cells in order up, right, down, and left.
32        for (int t = 0; t < 4; ++t) {
33            int nextRow = row + directions[t];
34            int nextCol = col + directions[t + 1];
35          
36            // Perform DFS for the next cell with one less remaining move.
37            pathCount += dfs(nextRow, nextCol, remainingMoves - 1);
38          
39            // Take modulo after each addition to prevent overflow.
40            pathCount %= MOD;
41        }
42
43        // Cache the result in the memoization table before returning.
44        memo[row][col][remainingMoves] = pathCount;
45        return pathCount;
46    }
47};
48

1// Define maxRowCount and maxColCount to track the grid dimensions.
2let maxRowCount: number;
3let maxColCount: number;
4
5// Define MOD as a constant to take modulo after additions to prevent overflow.
6const MOD: number = 1e9 + 7;
7
8// Initialize memoization table to store intermediate results.
9let memo: number[][][] = [];
10
11// Directions array to facilitate DFS moves: Up, Right, Down, Left.
12const directions: number[] = [-1, 0, 1, 0, -1];
13
14// Function to find the number of possible paths which move out of boundary.
15function findPaths(m: number, n: number, maxMove: number, startRow: number, startColumn: number): number {
16    // Initialize the memoization table with '-1' to indicate uncomputed states.
17    memo = [...Array(51)].map(() => [...Array(51)].map(() => Array(51).fill(-1)));
18  
19    // Set up the grid dimensions.
20    maxRowCount = m;
21    maxColCount = n;
22  
23    // Initiate DFS and return the resultant path count.
24    return dfs(startRow, startColumn, maxMove);
25}
26
27// Helper method for performing DFS traversal to compute path counts.
28function dfs(row: number, col: number, remainingMoves: number): number {
29    // If the cell is out of boundary, return 1 as we found a path out.
30    if (row < 0 || row >= maxRowCount || col < 0 || col >= maxColCount) return 1;
31
32    // Return cached result if this state has already been computed.
33    if (memo[row][col][remainingMoves] !== -1) return memo[row][col][remainingMoves];
34  
35    // If no more moves are left, return 0 as no further path can be made.
36    if (remainingMoves === 0) return 0;
37
38    // Variable to keep track of the number of paths from the current cell.
39    let pathCount: number = 0;
40  
41    // Iterate over all 4 potential moves (Up, Right, Down, Left).
42    for (let i = 0; i < 4; i++) {
43        let nextRow = row + directions[i];
44        let nextCol = col + directions[i + 1];
45      
46        // Recursive DFS call for the adjacent cell with one less remaining move.
47        pathCount += dfs(nextRow, nextCol, remainingMoves - 1);
48      
49        // Taking modulo to prevent integer overflow.
50        pathCount %= MOD;
51    }
52  
53    // Cache the computed result in the memo table before returning.
54    memo[row][col][remainingMoves] = pathCount;
55    return pathCount;
56}
57

Time and Space Complexity

The time complexity of the given code is O(m * n * maxMove). Each state in the dynamic programming (the dfs function is essentially dynamic programming with memoization due to the @cache decorator) is defined by three parameters: the current row i, the current column j, and the remaining number of moves k. There are m rows, n columns, and maxMove possible remaining moves. For each state, we perform a constant amount of work (exploring 4 adjacent cells), hence the total number of states multiplied by the constant gives us the time complexity.

The space complexity is also O(m * n * maxMove) because we need to store the result for each state to avoid recomputation. The space is used by the cache that stores intermediate results of the dfs function for each of the states characterized by the (i, j, k) triplet.

Learn more about how to find time and space complexity quickly using problem constraints.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using input 56?

1KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12def letter_combinations_of_phone_number(digits):
13    def dfs(path, res):
14        if len(path) == len(digits):
15            res.append(''.join(path))
16            return
17
18        next_number = digits[len(path)]
19        for letter in KEYBOARD[next_number]:
20            path.append(letter)
21            dfs(path, res)
22            path.pop()
23
24    res = []
25    dfs([], res)
26    return res
27

1private static final Map<Character, char[]> KEYBOARD = Map.of(
2    '2', "abc".toCharArray(),
3    '3', "def".toCharArray(),
4    '4', "ghi".toCharArray(),
5    '5', "jkl".toCharArray(),
6    '6', "mno".toCharArray(),
7    '7', "pqrs".toCharArray(),
8    '8', "tuv".toCharArray(),
9    '9', "wxyz".toCharArray()
10);
11
12public static List<String> letterCombinationsOfPhoneNumber(String digits) {
13    List<String> res = new ArrayList<>();
14    dfs(new StringBuilder(), res, digits.toCharArray());
15    return res;
16}
17
18private static void dfs(StringBuilder path, List<String> res, char[] digits) {
19    if (path.length() == digits.length) {
20        res.add(path.toString());
21        return;
22    }
23    char next_digit = digits[path.length()];
24    for (char letter : KEYBOARD.get(next_digit)) {
25        path.append(letter);
26        dfs(path, res, digits);
27        path.deleteCharAt(path.length() - 1);
28    }
29}
30

1const KEYBOARD = {
2    '2': 'abc',
3    '3': 'def',
4    '4': 'ghi',
5    '5': 'jkl',
6    '6': 'mno',
7    '7': 'pqrs',
8    '8': 'tuv',
9    '9': 'wxyz',
10}
11
12function letter_combinations_of_phone_number(digits) {
13    let res = [];
14    dfs(digits, [], res);
15    return res;
16}
17
18function dfs(digits, path, res) {
19    if (path.length === digits.length) {
20        res.push(path.join(''));
21        return;
22    }
23    let next_number = digits.charAt(path.length);
24    for (let letter of KEYBOARD[next_number]) {
25        path.push(letter);
26        dfs(digits, path, res);
27        path.pop();
28    }
29}
30

["jk", "mno"]

["jm", "kn", "lo"]

["jklmnp"]

["jm","jn","jo","km","kn","ko","lm","ln","lo"]

I don’t know