Out of Boundary Paths — Leetcode 576

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

Example 1:

Input: m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
Output: 6

Example 2:

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

Constraints:

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow < m
• 0 <= startColumn < n

Recursive + Memoization

import java.util.HashMap;
import java.util.Map;

class Solution {
    private static final int MOD = 1000000007;

    // Main method that is called by the user
    public int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
        // Create a memoization map
        Map<String, Integer> memo = new HashMap<>();
        
        // Call the helper method to perform the recursive calculation
        return helper(m, n, maxMove, startRow, startColumn, memo);
    }

    // Helper method for recursive calculation
    private int helper(int m, int n, int moves, int row, int col, Map<String, Integer> memo) {
        // Base case: Check if the robot is out of the grid boundaries
        if (row < 0 || col < 0 || row >= m || col >= n) {
            return 1; // Return 1 to signify a valid path out of the grid
        }

        // Base case: Check if there are no moves left
        if (moves == 0) {
            return 0; // Return 0 as there are no more moves to make
        }

        // Check if the result for the current state is already memoized
        String key = row + "," + col + "," + moves;
        if (memo.containsKey(key)) {
            return memo.get(key); // Return the memoized result
        }

        // Initialize paths variable to store the total number of paths from the current state
        int paths = 0;

        // Recursive calls for all possible moves: up, down, left, right
        // Update the paths variable with the results of the recursive calls
        paths = (paths + helper(m, n, moves - 1, row - 1, col, memo)) % MOD;
        paths = (paths + helper(m, n, moves - 1, row + 1, col, memo)) % MOD;
        paths = (paths + helper(m, n, moves - 1, row, col - 1, memo)) % MOD;
        paths = (paths + helper(m, n, moves - 1, row, col + 1, memo)) % MOD;

        // Memoize the result before returning
        memo.put(key, paths);

        // Return the total number of paths from the current state
        return paths;
    }
}

Time Complexity:

The time complexity of this recursive solution without memoization is exponential, O(4^maxMove), as each recursive call explores four possible moves. However, with memoization, the time complexity is reduced to O(m * n * maxMove), as each unique state is memoized.