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.
- Right -> Down -> Down
- Down -> Down -> Right
- 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
- Firstly, we will check if any cell from m and is equal to 1. Then, there will be only one path.
- Recursively find the number of paths possible.
-
To get the diagonal movements as well, we can add the following:
- + CountPaths(m-1, n-1);
- 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
- Create 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.
- Use a bottom-up approach to compute paths possible for other cells.
-
If you want to include diagonal movements also, then add the following:
- + count[i-1][j-1];
- 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
- Create a 1-D matrix for tabulating the results for smaller subproblems.
- Initialize all the elements of the array with 1.
- Create a nested for loop and apply this: dp[j] += dp[j - 1] where 0<j<1.
- 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
- Computing the value of m+n-2 C n-1 which equals to (m+n-2) / ((n-1)! * (m-1)!).
- Initialize the path as 1.
- Apply a for loop to calculate the path.
- 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:
- Minimum Edit Distance
- WAP to Count no. of alphabets, digits and spaces present in a file
- Majority Element
- Check for pairs in an array with a particular sum
- WAP to Print Triangle Using * Character
- Check if a subarray with 0 sum exists or not
- Data Structure & Algorithm: Interpolation Search
- Tree Data Structure & Algorithm
- What is Shell Sort?
- Doubly Linked List
Leave a Comment on this Post