Count all paths in a matrix from the first cell to the last cell
Given an M × N rectangular grid, efficiently count all paths starting from the first cell (0, 0) to the last cell (M-1, N-1). We can either move down or move towards right from a cell.
For example,
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 recur for the next cell, which can be either the immediate right cell or the immediate bottom cell. We can easily maintain the path count as we move along in the recursion, as demonstrated below in C, Java, and Python:
C
|
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 |
#include <stdio.h> // Top-down recursive function to count all paths from cell (m, n) // to the last cell (M-1, N-1) in a given `M × N` rectangular grid int countPaths(int m, int n, int M, int N) { // there is only one way to reach the last cell // when we are at the last row or the last column if (m == M - 1 || n == N - 1) { return 1; } return countPaths(m + 1, n, M, N) // move down + countPaths(m, n + 1, M, N); // move right } int main(void) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(0, 0, M, N); printf("The total number of paths is %d", k); return 0; } |
Output:
The total number of paths is 6
Java
|
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 |
class Main { // Top-down recursive function to count all paths from cell (m, n) // to the last cell (M-1, N-1) in a given `M × N` rectangular grid public static int countPaths(int m, int n, int M, int N) { // there is only one way to reach the last cell // when we are at the last row or the last column if (m == M - 1 || n == N - 1) { return 1; } return countPaths(m + 1, n, M, N) // move down + countPaths(m, n + 1, M, N); // move right } public static void main(String[] args) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(0, 0, M, N); System.out.println("The total number of paths is " + k); } } |
Output:
The total number of paths is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
# Top-down recursive function to count all paths from cell (m, n) # to the last cell (M-1, N-1) in a given `M × N` rectangular grid def countPaths(M, N, m=0, n=0): # there is only one way to reach the last cell # when we are at the last row or the last column if m == M - 1 or n == N - 1: return 1 # move down or right return countPaths(M, N, m + 1, n) + countPaths(M, N, m, n + 1) if __name__ == '__main__': # `M × N` matrix M = N = 3 k = countPaths(M, N) print("Total number of paths are", k) |
Output:
The total number of paths is 6
The time complexity of the proposed solution is exponential since it exhibits overlapping subproblems, i.e., it computes solutions to the same subproblems repeatedly. The problem also has an optimal substructure as the solution to the problem can be derived using a solution to its subproblems. Since both dynamic programming properties are satisfied, we can use it 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 subproblems. The following code follows the later approach:
C
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
#include <stdio.h> // Bottom-up function to count all paths from the first cell (0, 0) // to the last cell (M-1, N-1) in a given `M × N` rectangular grid int countPaths(int m, int n) { // `T[i][j]` stores the number of paths from cell (0, 0) to cell (i, j) int T[m][n]; // There is only one way to reach any cell in the first column // i.e., to move down for (int i = 0; i < m; i++) { T[i][0] = 1; } // There is only one way to reach any cell in the first row // i.e., to move right for (int j = 0; j < n; j++) { T[0][j] = 1; } // fill `T[][]` in a bottom-up manner for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { T[i][j] = T[i-1][j] + T[i][j-1]; } } // last cell of `T[][]` stores the count of paths from cell (0, 0) to // cell (i, j) return T[m-1][n-1]; } int main(void) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(M, N); printf("The total number of paths is %d", k); return 0; } |
Output:
The total number of paths is 6
Java
|
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 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
class Main { // Bottom-up function to count all paths from the first cell (0, 0) // to the last cell (M-1, N-1) in a given `M × N` rectangular grid public static int countPaths(int m, int n) { // `T[i][j]` stores the number of paths from cell (0, 0) to cell (i, j) int[][] T = new int[m][n]; // There is only one way to reach any cell in the first column, i.e., // to move down for (int i = 0; i < m; i++) { T[i][0] = 1; } // There is only one way to reach any cell in the first row, i.e., // to move right for (int j = 0; j < n; j++) { T[0][j] = 1; } // fill `T[][]` in a bottom-up manner for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { T[i][j] = T[i-1][j] + T[i][j-1]; } } // last cell of `T[][]` stores the count of paths from cell (0, 0) to // cell (i, j) return T[m-1][n-1]; } public static void main(String[] args) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(M, N); System.out.println("The total number of paths is " + k); } } |
Output:
The total number of paths is 6
Python
|
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 29 30 31 32 33 |
# Bottom-up function to count all paths from the first cell (0, 0) # to the last cell (M-1, N-1) in a given `M × N` rectangular grid def countPaths(m, n): # `T[i][j]` stores the number of paths from cell (0, 0) to cell (i, j) T = [[0 for x in range(n)] for y in range(m)] # There is only one way to reach any cell in the first column, i.e., to move down for i in range(m): T[i][0] = 1 # There is only one way to reach any cell in the first row, i.e., to move right for j in range(n): T[0][j] = 1 # fill `T` in a bottom-up manner for i in range(1, m): for j in range(1, n): T[i][j] = T[i-1][j] + T[i][j-1] # last cell of `T[][]` stores the count of paths from cell (0, 0) to cell # (i, j) return T[m-1][n-1] if __name__ == '__main__': # `M × N` matrix M = N = 3 k = countPaths(M, N) print("The total number of paths is", k) |
Output:
The total number of paths is 6
The time complexity of the proposed solution is O(M × N) for an M × N matrix. The auxiliary space required by the program is O(M × N). The space complexity of the solution can be improved up to O(N) as we are only reading data of the previous row for filling the current row. Following is the space-optimized solution using only a single array:
C
|
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 29 30 31 32 |
#include <stdio.h> // Bottom-up space-efficient function to count all paths from the first // cell (0, 0) to the last cell (M-1, N-1) in a given `M × N` rectangular grid int countPaths(int m, int n) { int T[n]; T[0] = 1; // fill `T[][]` in a bottom-up manner for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { T[j] += T[j - 1]; } } // return the last cell return T[n-1]; } int main(void) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(M, N); printf("The total number of paths is %d", k); return 0; } |
Output:
The total number of paths is 6
Java
|
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 29 30 31 |
class Main { // Bottom-up space-efficient function to count all paths from the first // cell (0, 0) to the last cell (M-1, N-1) in a given `M × N` rectangular grid public static int countPaths(int m, int n) { int[] T = new int[n]; T[0] = 1; // fill `T[][]` in a bottom-up manner for (int i = 0; i < m; i++) { for (int j = 1; j < n; j++) { T[j] += T[j - 1]; } } // return the last cell return T[n-1]; } public static void main(String[] args) { // `M × N` matrix int M = 3; int N = 3; int k = countPaths(M, N); System.out.print("The total number of paths is " + k); } } |
Output:
The total number of paths is 6
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
# Bottom-up space-efficient function to count all paths from the first # cell (0, 0) to the last cell (M-1, N-1) in a given `M × N` rectangular grid def countPaths(m, n): T = [0] * N T[0] = 1 # fill `T` in a bottom-up manner for i in range(m): for j in range(1, n): T[j] = T[j] + T[j - 1] # return the last cell return T[n-1] if __name__ == '__main__': # `M × N` matrix M = N = 3 k = countPaths(M, N) print("The total number of paths is", k) |
Output:
The total number of paths is 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 the right. So, the total number of ways are (m+n-2)C(n-1) or (m+n-2)C(m-1).
Exercise: Extend the solution for diagonal moves (down-right).
Suggested Post:
Find all paths from the first cell to the last cell of a matrix
Count the number of paths in a matrix with a given cost to reach the destination cell
Find the total number of unique paths in a maze from source to destination
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)