Count all paths in a matrix from first cell to last cell

Given a M x N rectangular grid, efficiently count all paths starting from the first cell (0,0) to the last cell (N-1,M-1) in the grid. We can either move down, or move towards right from a cell.


 

For example,


Input: 3 x 3 matrix

Output: Total number of paths are 6


(0, 0) -> (0, 1) -> (0, 2) -> (1, 2) -> (2, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (1, 2) -> (2, 2)
(0, 0) -> (0, 1) -> (1, 1) -> (2, 1) -> (2, 2)
(0, 0) -> (1, 0) -> (2, 0) -> (2, 1) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (1, 2) -> (2, 2)
(0, 0) -> (1, 0) -> (1, 1) -> (2, 1) -> (2, 2)

 
The idea is to start from the top-left corner of the matrix and recurse for the next cell which can be either immediate right cell or immediate bottom cell. We can easily maintain the path count as we move along in the recursion as shown below.

 

Download   Run Code

Output:

Total number of paths are: 6

 
The time complexity of above solution is exponential since the problem exhibits overlapping subproblems i.e. it computes solutions to the same sub-problems again and again. The problem also has an optimal substructure as solution to the problem can be derived using solution to its sub-problems. Now since both properties of dynamic programming are satisfied, it can be used to optimize the code.

We can either store results of the function calls and return those results when the same input occurs again or construct an auxiliary matrix to store results of the smaller sub-problems. Below code follows the later approach:

 

Download   Run Code

Output:

Total number of paths are: 6

 
The time complexity of the above solution is O(M x N) and the auxiliary space required by the program is O(M x N). The space complexity of the solution can be improved up to O(N) as we’re only reading data of previous row for filling the current row. Below is the space optimized solution using only single array.

 

Download   Run Code

Output:

Total number of paths are: 6

 
We can also find the number of paths from the first cell (0,0) to the last cell (m-1,n-1) using a direct formula. To reach the last cell, we have to take (m-1) steps to the right and (n-1) steps down. So the total steps are (m-1)+(n-1) = m+n-2. Out of these (m+n-2) steps, any (n-1) steps can be down and any (m-1) steps can be towards right. So, the total number of ways are (m+n-2)C(n-1) or (m+n-2)C(m-1).

 
 
Suggested Post: How to print all paths from first cell to last cell

 
Exercise: Extend the solution for diagonal moves (down-right).

 
Thanks for reading.

Please use our online compiler to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 


Leave a Reply

avatar
  Subscribe  
Notify of