576. Out of Boundary Paths - Explanation

1. Recursion

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        ROWS, COLS = m, n
        MOD = 10**9 + 7

        def dfs(r, c, moves):
            if r < 0 or r >= ROWS or c < 0 or c >= COLS:
                return 1
            if moves == 0:
                return 0

            return (
                dfs(r + 1, c, moves - 1) +
                dfs(r - 1, c, moves - 1) +
                dfs(r, c + 1, moves - 1) +
                dfs(r, c - 1, moves - 1)
            ) % MOD

        return dfs(startRow, startColumn, maxMove)

Time & Space Complexity

Time complexity: $O(4 ^ N)$
Space complexity: $O(N)$

Where $m$ is the number of rows, $n$ is the number of columns, and $N$ is the maximum number of allowed moves.

2. Dynamic Programming (Top-Down)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        ROWS, COLS = m, n
        MOD = 10**9 + 7
        cache = {}

        def dfs(r, c, moves):
            if r < 0 or r >= ROWS or c < 0 or c >= COLS:
                return 1
            if moves == 0:
                return 0
            if (r, c, moves) in cache:
                return cache[(r, c, moves)]

            cache[(r, c, moves)] = (
                dfs(r + 1, c, moves - 1) +
                dfs(r - 1, c, moves - 1) +
                dfs(r, c + 1, moves - 1) +
                dfs(r, c - 1, moves - 1)
            ) % MOD
            return cache[(r, c, moves)]

        return dfs(startRow, startColumn, maxMove)

Time & Space Complexity

Time complexity: $O(m * n * N)$
Space complexity: $O(m * n * N)$

Where $m$ is the number of rows, $n$ is the number of columns, and $N$ is the maximum number of allowed moves.

3. Dynamic Programming (Bottom-Up)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dp = [[[0] * (maxMove + 1) for _ in range(n)] for _ in range(m)]

        for moves in range(1, maxMove + 1):
            for r in range(m):
                for c in range(n):
                    dp[r][c][moves] = (
                        (dp[r - 1][c][moves - 1] if r > 0 else 1) +
                        (dp[r + 1][c][moves - 1] if r < m - 1 else 1) +
                        (dp[r][c - 1][moves - 1] if c > 0 else 1) +
                        (dp[r][c + 1][moves - 1] if c < n - 1 else 1)
                    ) % MOD

        return dp[startRow][startColumn][maxMove]

Time & Space Complexity

Time complexity: $O(m * n * N)$
Space complexity: $O(m * n * N)$

Where $m$ is the number of rows, $n$ is the number of columns, and $N$ is the maximum number of allowed moves.

4. Dynamic Programming (Space Optimized)

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * n for _ in range(m)]

        for moves in range(1, maxMove + 1):
            tmp = [[0] * n for _ in range(m)]
            for r in range(m):
                for c in range(n):
                    if r + 1 == m:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r + 1][c]) % MOD
                    if r - 1 < 0:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r - 1][c]) % MOD
                    if c + 1 == n:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r][c + 1]) % MOD
                    if c - 1 < 0:
                        tmp[r][c] = (tmp[r][c] + 1) % MOD
                    else:
                        tmp[r][c] = (tmp[r][c] + dp[r][c - 1]) % MOD
            dp = tmp

        return dp[startRow][startColumn]

Time & Space Complexity

Time complexity: $O(m * n * N)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows, $n$ is the number of columns, and $N$ is the maximum number of allowed moves.