algoadvance

Leetcode 576. Out of Boundary Paths

Problem Statement

Given an m x n grid and a ball that is initially at the position (startRow, startColumn), you are allowed to move the ball to any of the four adjacent cells in the grid (possibly out of the grid boundary). You can apply at most maxMove moves to the ball.

Given the five integers m, n, maxMove, startRow, and startColumn, return the number of ways to move the ball out of the grid boundary. Since the answer can be very large, return it modulo 10^9 + 7.

Clarifying Questions

  1. Can we assume that the inputs will always be valid?
    • Yes, you can assume that the inputs will always be within the specified constraints.
  2. What should we return if the ball cannot be moved out of the grid irrespective of maxMove?
    • You should return 0 in such cases.
  3. Are diagonal moves allowed?
    • No, only moves in the four cardinal directions (up, down, left, right) are allowed.
  4. Is it possible for maxMove to be 0, and if so, what should the output be?
    • Yes, if maxMove is 0, then the output should be 0 if the starting position is within the grid, because no moves are available to move the ball out of the boundary.

Strategy

  1. This problem can be efficiently solved using dynamic programming (DP).
  2. Define a DP table dp[move][i][j] where:
    • move is the number of moves taken so far.
    • (i, j) represents the cell position in the grid.
    • dp[move][i][j] is the number of ways to reach the boundary from cell (i, j) within move moves.
  3. Initialize the DP table such that any position outside the boundary contributes to moving out of the boundary in 0 moves.
  4. Iterate through possible moves and update the number of ways to reach out-of-bound positions from each cell using previous states.
  5. Use modular arithmetic to prevent overflow as per the problem constraints.

Code

public class Solution {
    private static final int MOD = 1000000007;

    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        int[][][] dp = new int[maxMove + 1][m][n];
    
        int[] directions = {-1, 0, 1, 0, -1}; // For moving in 4 directions
    
        // Iterate over number of moves
        for (int move = 1; move <= maxMove; move++) {
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    for (int d = 0; d < 4; d++) {
                        int x = i + directions[d];
                        int y = j + directions[d + 1];
                        if (x >= 0 && x < m && y >= 0 && y < n) {
                            dp[move][i][j] = (dp[move][i][j] + dp[move - 1][x][y]) % MOD;
                        } else {
                            dp[move][i][j] = (dp[move][i][j] + 1) % MOD;
                        }
                    }
                }
            }
        }
    
        return dp[maxMove][startRow][startColumn];
    }
}

Time Complexity

This algorithm ensures we efficiently compute the number of ways to move the ball out of the grid within the allowed moves, considering all possible paths and updates in a dynamic programming fashion.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI