Problem 576

(Last updated: )

Question statement:

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$.

Solution

The approach I opted for this problem is a 3-d dp approach.

Main idea:

Create an m x n 2-d dp array with the idea that we store at dp[i][j] a list whose index [k] stores the number of paths from (i,j) to a boundary if you have k-moves left over. Suppose we are at index (i,j) and we have k moves left over, now we can do one of four things

  • We can move up.
    • If we are at the edge, then moving up takes us out of the field, so increment dp by 1
    • If we are not at the edge, then we use one move to move up. So, increment dp[i][j] with dp[k-1][i-1][j]
  • We can move left.
    • If we are at the edge, then moving left takes us out of the field, so increment dp by 1
    • If we are not at the edge, then we use one move to move left. So, increment dp[i][j] with dp[k-1][j-1][k-1]
      and similarly to the right and down.

Note: We need compute all four possibilities when we are index [i][j]. Also, notice that k is the outermost loop because we need to compute the number of paths to get to the boundary with k-1 steps in order to compute the possibilities for the k-step case.

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
    num_paths = 0
    MOD = 7+10**9
    dp = [[[0 for _ in range(n)] for _ in range(m)] for _ in range(maxMove+1)]
    for k in range(1,maxMove+1):
        for i in range(m):
            for j in range(n):
                if(i==0):
                    dp[k][i][j]+=1
                else:
                    dp[k][i][j] += dp[k-1][i-1][j] % MOD
                
                if(i==m-1):
                    dp[k][i][j] +=1
                else:
                    dp[k][i][j] += dp[k-1][i+1][j] % MOD
                
                if(j==0):
                    dp[k][i][j]+=1
                else:
                    dp[k][i][j] += dp[k-1][i][j-1] % MOD
                
                if(j==n-1):
                    dp[k][i][j]+=1
                else:
                    dp[k][i][j] += dp[k-1][i][j+1] % MOD 
    
    return dp[-1][startRow][startColumn] % MOD

Comments:

Time complexity: O($n^3$) where n = max(m,n,maxMove)

At the time of submission, the above solution passes leetcode submission cases in 164ms, beats 10.27% of users. It uses 21.53MB of memory, beating 53.05% of users.