Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
1.1.
Problem Statement
1.2.
Sample Example
2.
Approach
2.1.
Steps of Algorithm
3.
Implementation in C++
3.1.
Complexity Analysis
4.
FAQs
5.
Key takeaways
Last Updated: Mar 27, 2024
Easy

Count of all unique paths from given source to destination in a Matrix

Author Harsh Goyal
0 upvote
Roadmap to SDE career at Amazon
Speaker
Anubhav Sinha
SDE-2 @
25 Jun, 2024 @ 01:30 PM

Introduction 

This blog will discuss the approach to return the count of all unique paths from a given source to destination in a Matrix. Before jumping on the approach to return the count of all unique paths from a given source to destination in a Matrix, let’s first understand what is the problem,

Must recommended topic about, kth largest element in an array, and Euclid GCD Algorithm

Problem Statement

In this problem, we’ll be provided with the source and destination in the 2D matrix, and we need to return the total number of the possible unique path to reach the destination by moving in the down or right direction only.

Sample Example

Input:

1

2

3

4

5

6

7

8

9

Source: {0 , 0}

Destination: {2, 2}

Output:

6

Explanation:

All unique paths possible are :-

1 -> 2 -> 3 -> 6 -> 9

1 -> 2 -> 5 -> 6 -> 9

1 -> 2 -> 5 -> 8 -> 9

1 -> 4 -> 5 -> 6 -> 9

1 -> 4 -> 5 -> 8 -> 9

1 -> 4 -> 7 -> 8 -> 9

Approach

This approach considers recursion which is used to move in the allowed direction ie. Right and down from each cell. In this way, when we reach the destination, we need to increment the count of possible unique paths.

Steps of Algorithm

Step 1. Call a ‘getResult’ function, which takes 5 parameters, 4 integer parameters ie. the x and y coordinates of the source, and destination cell and the fifth is the count integer variable to store the count of possible unique paths.

Step 2. In this function, check for the base case, in which if the x1, y1 is equal to x2, y2, which means we reached the destination, then increment the count variable and return count.

Step 3. If the base is not triggered then, make a recursive call for right movement by passing the y1 as y1 + 1 and assigning the returned integral value to count. 

Step 4. Now again make a recursive call for left movement by passing the x1 as x1 + 1 and assigning the returned integral value to count.

Step 5. Return the count variable.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Implementation in C++

#include <bits/stdc++.h>
using namespace std;

// Function to get the result
int getResult(int x1, int y1, int x2, int y2, int count)
{
   // Meeting the destination
   if (x1 == x2 || y1 == y2)
   {
       count++;
       return count;
   }

   // All unique paths using Right Movement
   count = getResult(x1, y1 + 1, x2, y2, count);

   // All unique paths using Down Movement
   count = getResult(x1 + 1, y1, x2, y2, count);

   return count;
}

int main()
{
   vector<vector<int> > input = { { 1, 2, 3 },
                               { 4, 5, 6 } ,
                               {7,8,9}};
   int x1 = 0, y1 = 0;
   int x2 = 2, y2 = 2;
   cout << "Total Number of Unique paths are:- ";
   cout << getResult(x1, y1, x2, y2, 0) << endl;
   return 0;
}

 

Output:

Total Number of Unique paths are:- 6

 

Complexity Analysis

Time Complexity: O(2 ^ max(M, N))

Incall to ‘getResult()’, we are checking each cell of the matrix by right and down movement only with the help of recursion and backtracking, and in this code, for F(M, N), we go for F(M + 1, N) and F(M, N + 1), that means two cases for each state, therefore the overall time complexity is O(2 ^ max(N * M)), where ‘N’ and ‘M’ are the total numbers of columns and rows of the matrix respectively.

Space Complexity: O(M + N)

As recursion uses extra space and in this case, a recursion tree will be formed with branch factor two, and the space used will be the maximum depth of the recursion tree, therefore the overall space complexity is O(M + N), where ‘M’ and ‘N’ are the total number of columns and rows of the matrix respectively.

FAQs

  1. Can we interchange the order of the recursive calls made in code?
    Yes, we can interchange the order of the recursive calls made in the code because we are checking all the paths which we can traverse with only right and down movement.
     
  2. What is another way to return the solution without explicitly using the ‘count’ variable?
    We can simply return 1 when we reach the destination and in other cases, we need to return the sum of the value received from both the recursive calls.
     
  3. Can we use sorting for this problem?
    No, we can’t use sorting for this problem as it will not solve or make us easy to solve our problem.
     
  4. What is the use of stack in this problem?
    Stack is used in the recursion. It is used to store and restore the recursive function and its arguments.

Key takeaways

In this article, we discussed the What is Count of all unique paths from a given source to destination in a Matrix problem, discussed the approach to solve this problem programmatically, the time and space complexities

Recommended Problems:

If you think that this blog helped you share it with your friends!. Refer to the DSA C++ course for more information.

Until then, All the best for your future endeavors, and Keep Coding.

Previous article
Sort a Given Array by Swapping Only Pairs with GCD as 1
Next article
C++ Program To Print All Permutations Of A Given String
Live masterclass