Count all Possible Paths from Top Left to Bottom Right in a Matrix

Posted in

Count all Possible Paths from Top Left to Bottom Right in a Matrix
vinaykhatri

Vinay Khatri
Last updated on March 29, 2024

    You are given a matrix of m*n dimensions. You have to calculate the total number of possible paths which you can reach from the top left to the bottom right of the matrix. But you are only allowed to move either top or bottom from any cell. You will be provided the value of m and n as input.

    Example 1:

    Input: m = 3, n = 2
    Output: 3

    Explanation: If you clearly observe, there are a total of three possible ways in which you can reach from top left to bottom right while moving either in the top direction or in the bottom direction.

    1. Right -> Down -> Down
    2. Down -> Down -> Right
    3. Down -> Right -> Down

    So the output thus obtained is 3.

    Approach 1: Recursion

    This is a recursive approach to this problem. In this approach, firstly, we will check if any cell from m and is equal to 1. Then, there will be only one path. Then we will iterate the matrix recursively to find the number of paths possible. This is a naive approach and hence has exponential complexity.

    Algorithm

    1. Firstly, we will check if any cell from m and is equal to 1. Then, there will be only one path.
    2. Recursively find the number of paths possible.
    3. To get the diagonal movements as well, we can add the following:
      1. + CountPaths(m-1, n-1);
    4. Return the total number of paths.

    The implementation of the above-discussed approach is:

    CPP

    #include <iostream>
    using namespace std;
    
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    int CountPaths(int m, int n)
    {
      // if anyone from m and n
      // is equal to 1
      // then there will be only one path.
      if (m == 1 || n == 1)
        return 1;
    
      // recursively find the number of
      // paths possible.
      return CountPaths(m - 1, n) + CountPaths(m, n - 1);
      // if you want to include diagonal movements also, 
      // then uncomment the following.
      // + CountPaths(m-1, n-1);
    }
    
    int main()
    {
      cout << CountPaths(4, 4);
      return 0;
    }
    

    Output

    20

    JAVA

    class CountPaths {
    
    
      // function to return number of
      // all paths possible to
      // go from top left cell (1, 1)
      // to reach bottom most cell (m-1 , n-1)
      static int CountPaths(int m, int n)
      { // if anyone from m and n
        // is equal to 1
        // then there will be only one path.
        if (m == 1 || n == 1)
          return 1;
    
        // recursively find the number of
        // paths possible.
        return CountPaths(m - 1, n) + CountPaths(m, n - 1);
        // if you want to include diagonal movements also,
        // then uncomment the following.
        // + CountPaths(m-1, n-1);
      }
    
      public static void main(String args[])
      {
        System.out.println(CountPaths(4, 4));
      }
    }
    
    

    Output

    20

    Python

    # function to return the number of
    # all paths possible to 
    # go from the top-left cell (1, 1)
    # to reach bottom-most cell (m-1, n-1)
    def CountPaths(m, n):
    # if anyone from m and n
    # is equal to 1
    # then there will be only one path.
        if(m == 1 or n == 1):
            return 1
    
    # recursively find the number of
    # paths possible
        return CountPaths(m-1, n) + CountPaths(m, n-1)
    
    # Driver program to test above function
    m = 4
    n = 4
    print(CountPaths(m, n))
    

    Output

    20

    C#

    using System;
    
    public class CountPath {
        // function to return number of
        // all paths possible to 
        // go from top left cell (1, 1)
        // to reach bottom most cell (m-1 , n-1)
        static int CountPaths(int m, int n)
        {
            // if anyone from m and n
            // is equal to 1
            // then there will be only one path.
            if (m == 1 || n == 1)
                return 1;
    
            // recursively find the number of
            // paths possible.
            return CountPaths(m - 1, n) + CountPaths(m, n - 1);
            // if you want to include diagonal movements also, 
            // then uncomment the following.
            // + CountPaths(m-1, n-1);
        }
    
        static public void Main()
        {
            Console.WriteLine(CountPaths(4, 4));
        }
    }
    

    Output

    20

    PHP

    <?php
    
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    function CountPaths($m, $n)
    {
    
    // if anyone from m and n
    // is equal to 1
    // then there will be only one path.
    if ($m == 1 || $n == 1)
    return 1;
    
    // recursively find the number of
    // paths possible.
    return CountPaths($m - 1, $n) +
    CountPaths($m, $n - 1);
    }
    
    // Driver Code
    echo CountPaths(4, 4);
    
    ?>

    Output

    20

    Complexity Analysis

    Time Complexity : The time complexity of this approach is exponential, which is way too bad. This is because, due to recursion, there are many overlapping subproblems that result in repeated recursion calls, hence increasing the complexity.

    Approach 2: Dynamic Programming

    Since the above approach has exponential time complexity, we will talk about a better approach. In this approach, we will be creating a 2-D matrix for tabulating the results for smaller subproblems. The number of paths having a destination as any cell in column no. 1 will be 1. The number of paths having a destination as any cell in column no. 1 will be 1. Then we will use a bottom-up approach to compute paths possible for other cells and return the count.

    Algorithm

    1. Create a 2-D matrix for tabulating the results for smaller subproblems.
    2. The number of paths having a destination as any cell in column no. 1 will be 1.
    3. The number of paths having a destination as any cell in column no. 1 will be 1.
    4. Use a bottom-up approach to compute paths possible for other cells.
    5. If you want to include diagonal movements also, then add the following:
      1. + count[i-1][j-1];
    6. Return the count.

    The implementation of the above-discussed approach is:

    CPP

    #include <iostream>
    using namespace std;
    
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    int CountPaths(int m, int n)
    {
      // a 2-D matrix for tabulating the results
      // for smaller subproblems
      int count[m][n];
    
      // number of paths having destination as
      // any cell in the column no. 1 will be 1
      for (int i = 0; i < m; i++)
        count[i][0] = 1;
    
      // number of paths having destination as
      // any cell in the row no. 1 will be 1
      for (int j = 0; j < n; j++)
        count[0][j] = 1;
    
      // using bottom-up approach to compute paths 
      // possible for other cells.
      for (int i = 1; i < m; i++) {
        for (int j = 1; j < n; j++)
    
          // if you want to include diagonal movements also, 
          // then uncomment the following.
          count[i][j] = count[i - 1][j] + count[i][j - 1]; //+ count[i-1][j-1];
      }
      return count[m - 1][n - 1];
    }
    
    int main()
    {
      cout << CountPaths(4, 4);
      return 0;
    }
    

    Output

    20

    JAVA

    class CountPaths {
      
      // method to return number of
      // all paths possible to 
      // go from top left cell (1, 1)
      // to reach bottom most cell (m-1 , n-1)
      static int CountPaths(int m, int n)
      {
        // a 2-D matrix for tabulating the results
        // for smaller subproblems
        int count[][] = new int[m][n];
    
        // number of paths having destination as
        // any cell in the column no. 1 will be 1
        for (int i = 0; i < m; i++)
          count[i][0] = 1;
    
        // number of paths having destination as
        // any cell in the row no. 1 will be 1
        for (int j = 0; j < n; j++)
          count[0][j] = 1;
    
      
        // using bottom-up approach to compute paths 
        // possible for other cells.
        for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++)
    
            // if you want to include diagonal movements also, 
            // then uncomment the following.
            count[i][j] = count[i - 1][j] + count[i][j - 1]; //+ count[i-1][j-1];
        }
        return count[m - 1][n - 1];
      }
    
      public static void main(String args[])
      {
        System.out.println(CountPaths(4, 4));
      }
    }
    

    Output

    20

    Python

    # function to return number of
    # all paths possible to 
    # go from top left cell (1, 1)
    # to reach bottom most cell (m-1 , n-1)
    def CountPaths(m, n):
        # a 2-D matrix for tabulating the results
        # for smaller subproblems
        count = [[0 for x in range(m)] for y in range(n)]
    
        # number of paths having destination as
        # any cell in the column no. 1 will be 1
        for i in range(m):
            count[i][0] = 1;
    
        # number of paths having destination as
        # any cell in the row no. 1 will be 1
        for j in range(n):
            count[0][j] = 1;
    
        # using bottom-up approach to compute paths 
        # possible for other cells.
        for i in range(1, m):
            for j in range(1, n):           
                count[i][j] = count[i-1][j] + count[i][j-1]
        return count[m-1][n-1]
    
    # Driver program to test above function
    m = 4
    n = 4
    print( CountPaths(m, n))
    

    Output

    20

    C#

    using System;
    
    public class CountPath {
    
    	// method to return number of
    	// all paths possible to
    	// go from top left cell (1, 1)
    	// to reach bottom most cell (m-1 , n-1)
    	static int CountPaths(int m, int n)
    	{
        	// a 2-D matrix for tabulating the results
        	// for smaller subproblems
        	int[, ] count = new int[m, n];
    
        	// number of paths having destination as
        	// any cell in the column no. 1 will be 1
        	for (int i = 0; i < m; i++)
            	count[i, 0] = 1;
    
        	// number of paths having destination as
        	// any cell in the row no. 1 will be 1
        	for (int j = 0; j < n; j++)
            	count[0, j] = 1;
    
        	// using bottom-up approach to compute paths
        	// possible for other cells.
        	for (int i = 1; i < m; i++) {
            	for (int j = 1; j < n; j++)
    
                	// if you want to include diagonal movements also,
                	// then uncomment the following.
                	count[i, j] = count[i - 1, j] + count[i, j - 1]; //+ count[i-1][j-1];
        	}
        	return count[m - 1, n - 1];
    	}
    
    	// Driver program to test above function
    	static public void Main()
    	{
        	Console.WriteLine(CountPaths(4, 4));
    	}
    }
    

    Output

    20

    PHP

    <?php 
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    function CountPaths($m, $n)
    {
        // a 2-D matrix for tabulating the results
        // for smaller subproblems
        $count = array();
    
        // number of paths having destination as
        // any cell in the column no. 1 will be 1
        for ($i = 0; $i < $m; $i++)
            $count[$i][0] = 1;
    
        // number of paths having destination as
        // any cell in the row no. 1 will be 1
        for ($j = 0; $j < $n; $j++)
            $count[0][$j] = 1;
    
        // using bottom-up approach to compute paths 
        // possible for other cells.
        for ($i = 1; $i < $m; $i++)
        {
            for ($j = 1; $j < $n; $j++)
    
                // if you want to include diagonal movements also, 
                // then uncomment the following.
                $count[$i][$j] = $count[$i - 1][$j] +
                                $count[$i][$j - 1]; //+ count[i-1][j-1];
        }
        return $count[$m - 1][$n - 1];
    }
    
    // Driver Code
    echo CountPaths(4, 4);
    ?>

    Output

    20

    Complexity Analysis

    Time Complexity : O(m*n), where m is the size of the row and n is the size of the column. This is because we are simply iterating over a 2-D matrix, so the complexity will be O(m*n).

    Approach 3: DP with optimized space

    This approach is the optimized version of the above approach. This will reduce the space complexity from O(m*n) to O(n), where n is the column size. However, the time complexity of this approach will be the same as the previous approach. We will create a 1-D matrix for tabulating the results for smaller subproblems. And then, return the number of all paths possible to go from the top-left cell (1, 1) to reach the bottom-most cell (m-1, n-1).

    Algorithm

    1. Create a 1-D matrix for tabulating the results for smaller subproblems.
    2. Initialize all the elements of the array with 1.
    3. Create a nested for loop and apply this: dp[j] += dp[j - 1] where 0<j<1.
    4. Return the number of all paths possible to go from the top left cell (1, 1) to the bottom-most cell (m-1, n-1).

    The implementation of the above-discussed approach is:

    CPP

    #include <bits/stdc++.h>
    using namespace std;
    
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    int numberOfPaths(int m, int n)
    {
      // a 1-D matrix for tabulating the results
      // for smaller subproblems
      int dp[n] = { 1 };
      dp[0] = 1;
    
      for (int i = 0; i < m; i++) {
        for (int j = 1; j < n; j++) {
          dp[j] += dp[j - 1];
        }
      }
    
      return dp[n - 1];
    }
    
    // Driver code
    int main()
    {
      cout << numberOfPaths(4, 4);
    }
    

    Output

    20

    JAVA

    class CountPaths {
      
      // method to return number of
      // all paths possible to 
      // go from top left cell (1, 1)
      // to reach bottom most cell (m-1 , n-1)
      static int CountPaths(int m, int n)
      {
        // a 1-D matrix for tabulating the results
        // for smaller subproblems
        int[] dp = new int[n];
        dp[0] = 1;
    
        for (int i = 0; i < m; i++) {
          for (int j = 1; j < n; j++) {
            dp[j] += dp[j - 1];
          }
        }
    
        return dp[n - 1];
      }
    
      public static void main(String args[])
      {
        System.out.println(CountPaths(4, 4));
      }
    }
    

    Output

    20

    Python

    # function to return number of
    # all paths possible to 
    # go from top left cell (1, 1)
    # to reach bottom most cell (m-1 , n-1)
    def CountPaths(p, q):
        
        # a 1-D matrix for tabulating the results
        # for smaller subproblems
        dp = [1 for i in range(q)]
        for i in range(p - 1):
            for j in range(1, q):
                dp[j] += dp[j - 1]
        return dp[q - 1]
    
    # Driver Code
    print(CountPaths(4, 4))
    

    Output

    20

    C#

    using System;
    
    class CountPath {
        // function to return number of
        // all paths possible to 
        // go from top left cell (1, 1)
        // to reach bottom most cell (m-1 , n-1)
        static int CountPaths(int m, int n)
        {
            // a 1-D matrix for tabulating the results
            // for smaller subproblem
            int[] dp = new int[n];
            dp[0] = 1;
    
            for (int i = 0; i < m; i++) {
                for (int j = 1; j < n; j++) {
                    dp[j] += dp[j - 1];
                }
            }
    
            return dp[n - 1];
        }
    
        // Driver Code
        public static void Main()
        {
            Console.Write(CountPaths(4, 4));
        }
    }
    

    Output

    20

    Complexity Analysis

    Time Complexity : O(m*n), where m is the size of the row and n is the size of the column. This is because we are simply iterating over a 2-D matrix so the complexity will be O(m*n).

    Approach 4: Combinatorics

    In this approach, we will be using combinatorics. Combinatorics is a concept or field of mathematics, which is hugely focused on counting whether it is the method of the code or the return value. It has significant applications in the fields of mathematics such as logic. It is also widely used in computer science, statistical physics, and other important fields. Here we will be computing m+n-2 C n-1 here which will be (m+n-2)! / (n-1)! (m-1)! With the help of combinatorics. The implementation of the above-discussed approach is:

    Algorithm

    1. Computing the value of m+n-2 C n-1 which equals to (m+n-2) / ((n-1)! * (m-1)!).
    2. Initialize the path as 1.
    3. Apply a for loop to calculate the path.
    4. Return the path.

    CPP

    #include 
    using namespace std;
    
    // function to return number of
    // all paths possible to 
    // go from top left cell (1, 1)
    // to reach bottom most cell (m-1 , n-1)
    int CountPaths(int m, int n)
    {
        // computing the value of
        // m+n-2 C n-1
        // which equals to 
        // (m+n-2) / ((n-1)! * (m-1)!)
    	int path = 1;
    	for (int i = n; i < (m + n - 1); i++) {
    		path *= i;
    		path /= (i - n + 1);
    	}
    	return path;
    }
    
    // Driver code
    int main()
    {
    	cout << CountPaths(4, 4);
    	return 0;
    }
    

    Output

    20

    JAVA

    class CountPaths {
    
    	static int CountPaths(int m, int n)
    	{
    		// computing the value of
            // m+n-2 C n-1
            // which equals to 
            // (m+n-2) / ((n-1)! * (m-1)!)
    		int path = 1;
    		for (int i = n; i < (m + n - 1); i++) {
    			path *= i;
    			path /= (i - n + 1);
    		}
    		return path;
    	}
    
    	// Driver code
    	public static void main(String[] args)
    	{
    		System.out.println(CountPaths(4, 4));
    	}
    }
    

    Output

    20

    Python

    def CountPaths(m, n) :
    
        # computing the value of
        # m+n-2 C n-1
        # which equals to 
        # (m+n-2) / ((n-1)! * (m-1)!)
        path = 1
        for i in range(n, (m + n - 1)):
            path *= i;
            path //= (i - n + 1);
        
        return path;
    
    # Driver code
    print(CountPaths(4, 4));
    

    Output

    20

    C#

    using System;
    
    class CountPath {
    
        static int CountPaths(int m, int n)
        {
            // function to return number of
            // all paths possible to 
            // go from top left cell (1, 1)
            // to reach bottom most cell (m-1 , n-1)
            int path = 1;
            for (int i = n; i < (m + n - 1); i++) {
                path *= i;
                path /= (i - n + 1);
            }
            return path;
        }
    
        // Driver code
        public static void Main()
        {
            Console.WriteLine(CountPaths(4, 4));
        }
    }
    

    Output

    20

    PHP

    <?php
    function CountPaths($m, $n)
    {
        // function to return number of
        // all paths possible to 
        // go from top left cell (1, 1)
        // to reach bottom most cell (m-1 , n-1)
        $path = 1;
        for ($i = $n; $i < ($m + $n - 1); $i++)
        {
            $path *= $i;
            $path /= ($i - $n + 1);
        }
        return $path;
    }
    
    // Driver code
    {
        echo(CountPaths(4, 4));
    }
    ?>

    Output

    20

    Complexity Analysis

    Time Complexity : O(m + n), where m and n are the numbers of rows and columns given in the matrix.

    Wrapping Up!

    In this article, we have learned an amazing concept of 2-D arrays. Matrix is one of the most important data structures and is usually asked in the top interview questions as well. “Count all possible paths from top left to the bottom right in a matrix” is a popular as well as a very important problem that has been asked in various interview questions.

    In this article, we have included proper examples with detailed explanations for a better understanding for you. We also learned about how we should think of a solution and then make optimizations in our code for such kinds of problems.

    This blog covers four well-explained approaches along with some suitable examples to solve this problem. We also covered in detail how all four of the approaches work and what is their significance of them. We discussed their time complexity along with a proper explanation. Different programmers prefer different languages for coding. So, we made sure that all our readers could refer to this article.

    That’s why this article also contains well-explained codes for all the approaches in the three most popular languages, which are c++, Java, and Python, along with their respective outputs attached to the article for a better understanding of a wide range of our readers.

    We sincerely hope that this article has walked you through some deep and important concepts of Binary Trees and how we should approach such kinds of problems. We surely wish you to keep up your practice and crack all the questions easily. With this, we are wrapping up this article.

    Happy Learning!

    People are also reading:

    Leave a Comment on this Post

    0 Comments