Out of Boundary Paths Python Solution

Tested Python solution for LeetCode 576 with 14 pytest cases. Generate a practice environment with lcpy.

LeetCode 576, Medium. Topics: Dynamic Programming. View on LeetCode.

Generate this problem as a practice environment: tested reference solution, 14 parametrized pytest cases, and a playground notebook:

lcpy gen -n 576   # by problem number
lcpy gen -s out_of_boundary_paths   # by problem name

​

Problem

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 10^9 + 7.

​

Examples

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

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

​

Solution

Reference implementation from solution.py on GitHub, full suite in test_solution.py:

class Solution:
    # Time: O(max_move * m * n)
    # Space: O(m * n)
    def find_paths(
        self,
        m: int,
        n: int,
        max_move: int,
        start_row: int,
        start_column: int,
    ) -> int:
        mod = 1_000_000_007
        # dp[r][c]: number of paths currently at cell (r, c) inside the grid.
        dp = [[0] * n for _ in range(m)]
        dp[start_row][start_column] = 1
        paths = 0
        for _ in range(max_move):
            nxt = [[0] * n for _ in range(m)]
            for row in range(m):
                for col in range(n):
                    count = dp[row][col]
                    if not count:
                        continue
                    for n_row, n_col in (
                        (row + 1, col),
                        (row - 1, col),
                        (row, col + 1),
                        (row, col - 1),
                    ):
                        if 0 <= n_row < m and 0 <= n_col < n:
                            nxt[n_row][n_col] = (nxt[n_row][n_col] + count) % mod
                        else:
                            paths = (paths + count) % mod
            dp = nxt
        return paths

​

Complexity

Time	Space
O(max_move * m * n)	O(m * n)

​

Tags

NeetCode All.