576. Out of Boundary Paths


There is an m by n grid with a ball. Given the start coordinate (i,j) of the ball, you can move the ball to adjacent cell or cross the grid boundary in four directions (up, down, left, right). However, you can at most move N times. Find out the number of paths to move the ball out of grid boundary. The answer may be very large, return it after mod 109 + 7.

Example 1:

Input:m = 2, n = 2, N = 2, i = 0, j = 0
Output: 6
Explanation:

Example 2:

Input:m = 1, n = 3, N = 3, i = 0, j = 1
Output: 12
Explanation:

Note:

  1. Once you move the ball out of boundary, you cannot move it back.
  2. The length and height of the grid is in range [1,50].
  3. N is in range [0,50].


Summary

Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

In the brute force approach, we try to take one step in every direction and decrement the number of pending moves for each step taken. Whenever we reach out of the boundary while taking the steps, we deduce that one extra path is available to take the ball out.

In order to implement the same, we make use of a recursive function findPaths(m,n,N,i,j) which takes the current number of moves() along with the current position( as some of the parameters and returns the number of moves possible to take the ball out with the current pending moves from the current position. Now, we take a step in every direction and update the corresponding indices involved along with the current number of pending moves.

Further, if we run out of moves at any moment, we return a 0 indicating that the current set of moves doesn't take the ball out of boundary.

Complexity Analysis

  • Time complexity : . Size of recursion tree will be . Here, refers to the number of moves allowed.

  • Space complexity : . The depth of the recursion tree can go upto .

Approach #2 Recursion with memoization [Accepted]

Algorithm

In the brute force approach, while going through the various branches of the recursion tree, we could reach the same position with the same number of moves left.

Thus, a lot of redundant function calls are made with the same set of parameters leading to a useless increase in runtime. We can remove this redundancy by making use of a memoization array, . is used to store the number of possible moves leading to a path out of the boundary if the current position is given by the indices and number of moves left is .

Thus, now if a function call with some parameters is repeated, the array will already contain valid values corresponding to that function call resulting in pruning of the search space.

Complexity Analysis

  • Time complexity : . We need to fill the array once with dimensions xx. Here, , refer to the number of rows and columns of the given grid respectively. refers to the total number of allowed moves.

  • Space complexity : . array of size is used.

Approach #3 Dynamic Programming [Accepted]

Algorithm

The idea behind this approach is that if we can reach some position in moves, we can reach all its adjacent positions in moves. Based on this idea, we make use of a 2-D array to store the number of ways in which a particular position can be reached. refers to the number of ways the position corresponding to the indices can be reached given some particular number of moves.

Now, if the current array stores the number of ways the various positions can be reached by making use of moves, in order to determine the number of ways the position can be reached by making use of moves, we need to update the corresponding entry as taking care of boundary conditions. This happens because we can reach the index from any of the four adjacent positions and the total number of ways of reaching the index in moves is the sum of the ways of reaching the adjacent positions in moves.

But, if we alter the array, now some of the entries will correspond to moves and the updated ones will correspond to moves. Thus, we need to find a way to tackle this issue. So, instead of updating the array for the current() moves, we make use of a temporary 2-D array to store the updated results for moves, making use of the results obtained for array corresponding to moves. After all the entries for all the positions have been considered for moves, we update the array based on . Thus, now contains the entries corresponding to moves.

Thus, we start off by considering zero move available for which we make an initial entry of ( is the initial position), since we can reach only this position in zero move. Then, we increase the number of moves to 1 and update all the entries appropriately. We do so for all the moves possible from 1 to N.

In order to update , which indicates the total number of possible moves which lead an out of boundary path, we need to perform the update only when we reach the boundary. We update the count as , where corresponds to one of the boundaries. But, if is simultaneously a part of multiple boundaries, we need to add the factor multiple times(same as the number of boundaries to which belongs).

After we are done with all the moves, gives the required result.

The following animation illustrates the process:

!?!../Documents/576_Boundary_Paths.json:1000,563!?!

Complexity Analysis

  • Time complexity : . We need to fill the $ array with dimensions x times. Here x refers to the size of the grid and refers to the number of moves available.

  • Space complexity : . and array of size x are used.

Analysis written by: @vinod23

Submit Solution