algoadvance

Leetcode 576. Out of Boundary Paths

Problem Statement:

Given an m x n grid with a ball placed at the start location (i, j), count the number of ways the ball can move out of the grid boundary. The ball can move in any of the four possible directions (up, down, left, right) but must stay within the grid during each move. You are also given an integer N representing the number of maximum moves allowed.

Return the number of ways to move the ball out of the grid boundary with at most N moves. Since the answer can be large, return it modulo (10^9 + 7).

Clarifying Questions:

  1. Should the movements consider directions that immediately take the ball out of the boundary as valid moves?
    • Yes, moving the ball out of the boundary in any of the four directions is considered a valid move.
  2. What is the constraint on m, n, and N?
    • Typical constraints would be (1 \leq m, n \leq 50) and (0 \leq N \leq 50), giving us room to use dynamic programming solutions.

Strategy:

  1. State Representation:
    • We’ll use a 3D DP table dp[m][n][N+1] where dp[i][j][k] represents the number of ways to move the ball out of the boundary starting from cell (i, j) with k moves remaining.
  2. Base Case:
    • If i, j are out of bounds, then we’ve successfully moved the ball out, i.e., these contribute to the paths.
  3. Recurrence Relation:
    • For each cell (i, j) with k moves remaining, the new count of ways can be computed as the sum of ways from its neighboring cells (i-1, j), (i+1, j), (i, j-1), (i, j+1) with k-1 moves.
  4. Boundary Check:
    • If at any point the indices move out of the grid bounds, they directly contribute to the count by 1.

Code:

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int findPaths(int m, int n, int N, int i, int j) {
        const int MOD = 1e9 + 7;
        vector<vector<vector<int>>> dp(m, vector<vector<int>>(n, vector<int>(N + 1, 0)));
        
        for (int k = 1; k <= N; ++k) {
            for (int x = 0; x < m; ++x) {
                for (int y = 0; y < n; ++y) {
                    long long paths = 0;
                    if (x == 0) paths++; // moving from row 0 out of bounds
                    if (x == m - 1) paths++; // moving from last row out of bounds
                    if (y == 0) paths++; // moving from column 0 out of bounds
                    if (y == n - 1) paths++; // moving from last column out of bounds
                    
                    paths += (x > 0 ? dp[x-1][y][k-1] : 0) % MOD;
                    paths += (x < m-1 ? dp[x+1][y][k-1] : 0) % MOD;
                    paths += (y > 0 ? dp[x][y-1][k-1] : 0) % MOD;
                    paths += (y < n-1 ? dp[x][y+1][k-1] : 0) % MOD;
                    
                    dp[x][y][k] = paths % MOD;
                }
            }
        }
        
        return dp[i][j][N];
    }
};

int main() {
    Solution solution;
    cout << solution.findPaths(2, 2, 2, 0, 0) << endl; // Expected output: 6
    return 0;
}

Time Complexity:

This solution efficiently calculates the number of ways the ball can be moved out of the boundary considering the constraints.

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