Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Approach
2.1.
PseudoCode
3.
Implementation in C++
3.1.
Complexity Analysis
4.
Frequently Asked Questions
5.
Key Takeaways
Last Updated: Mar 27, 2024
Medium

Print all unique paths from a given source to destination in a Matrix moving only down or right

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

Introduction

In this blog, we will discuss a 2-D array problem asked frequently in Interviews.

The problem is to Print all unique paths from a given source to destination in a Matrix moving only down or right.

We are given an N X M matrix, a source coordinate and a destination coordinate. We need to print all possible paths to reach from source to destination.

Example: Say we have 2 X 3 matrix, source given is (0,0) and destination is (1,2)

We have to find all possible paths in which we can reach from source to destination.

Here we will get our answer as 3.

Also see, kth largest element in an array, and Euclid GCD Algorithm

Approach

The approach to Print all unique paths from a given source to destination in a Matrix moving only down or right can be explained by the recursion method.

In our example, we have 2 X 3 matrix. Source = 0,0 and Destination = 1,2.

Define the base case. If the current cell is out of bound then simply return.

If the destination is reached, then return 1.

Call the recursive function two times, one for the down cell and the other for the right cell with respect to the current cell.

So the recursion tree would be: 

Time Complexity = O(2^(n+m))

Space Complexity = O(1)

Till now, I assume you must have got the basic idea of what has been asked in the problem statement. So, I strongly recommend you first give it a try: Try here

Please have a look at the algorithm, and then again, you must give it a try.

PseudoCode

Algorithm

___________________________________________________________________

procedure countPaths(int i, int j, vector<int> path):

___________________________________________________________________

1.  if i > d[0] || j > d[1]: return

2.  path.push_back(i)

     path.push_back(j)

3.  if (i == d[0] && j == d[1]):

     printVector(path);

     return;

4.  countPaths(i, j + 1, path);

     countPaths(i + 1, j, path);

end procedure

___________________________________________________________________

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++

// C++ program to Print all unique paths from given source to destination in a Matrix moving only down or right
#include <bits/stdc++.h>
using namespace std;

vector<vector < int>> mat;
vector<int> s;
vector<int> d;
int m = 2, n = 3;

// Function to print all possible paths from given source to given destination  
void printVector(vector<int> path)
{
	int cnt = path.size();
	for (int i = 0; i < cnt; i += 2)
		cout << mat[path[i]][path[i + 1]] <<
		" ";
	cout << endl;
}

// Function to find all possible paths using recursion
void countPaths(int i, int j, vector<int> path)
{

	// Base Case
	if (i > d[0] || j > d[1])
		return;
	path.push_back(i);
	path.push_back(j);

	// When destination is reached
	if (i == d[0] && j == d[1])
	{
		printVector(path);
		return;
	}

	// Recursion
	countPaths(i, j + 1, path);
	countPaths(i + 1, j, path);
}

int main()
{
	mat = {
		{ 1, 2, 3 },
		{ 4, 5, 6 }
	};
	s = { 0, 0 };
	d = { 1, 2 };
	vector<int> path;

	countPaths(s[0], s[1], path);
	return 0;
}

 

Output

Sample Input: 
1 2 3
4 5 6
0,0
1,2
Sample Output:
1 2 3 6
1 2 5 6
1 4 5 6

 

Complexity Analysis

Time Complexity: O(2^(n+m)).

Analysing Time Complexity:

Since matrix consists of n+m elements and each element has 2 possibilities.

Space complexity: O(1).

Frequently Asked Questions

  1. When to use the backtracking method?
    Answer) Whenever there is some kind of decisive problem, we use the backtracking method.
     
  2. What is recursion? 
    Answer) The calling function itself, again and again, is referred to as recursion. To know more about recursion, click here.
     
  3. When to use recursion?
    Answer) When we can break the problem into smaller parts, we can use recursion. It also helps in reducing the complexity sometimes. 

Key Takeaways

This article taught us how to Print all unique paths from a given source to destination in a Matrix moving only down or right by approaching the problem using recursion and backtracking. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analyzing problems by walking over the execution of the examples and finding out the recursive pattern followed.

Now, we recommend you practice problem sets based on recursion to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types. 

Recommended Problems:

Happy Coding.

Previous article
Maximize Cost of Forming a Set of Words Using Given Set of Characters
Next article
Print All Paths from a Source Point to All the 4 Corners of a Matrix
Live masterclass