Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach 
4.
Code in C++
4.1.
Output
4.2.
Time Complexity
4.3.
Space Complexity
5.
Frequently Asked Questions
6.
Key Takeaways
Last Updated: Mar 27, 2024

Determine the longest path from the source cell to the destination cell in a matrix

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

Introduction

Before beginning with this question, let’s recap what a graph means. 

A graph is a non-linear data structure that contains edges that connect vertices.  

Graphs can be either directed or undirected. A directed graph consists of nodes/vertices connected by edges where each edge has a direction. The edges of a graph are represented using arrows pointing in the direction of traversal. If there is an arrow from 1 to 2, the graph can be traversed from 1 to 2 rather than 2 to 1. Whereas in an undirected graph, we can traverse in either direction, i.e., we can travel in the graph from 1 to 2 and 2 to 1 if the graph is undirected.

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

Problem Statement

You are given a matrix and the coordinates of the source and destination cells. Determine the longest path from the source cell to the destination cell in the matrix. Examples: 
 

Example 1: 
Input:  sourceCell = {0,1}      destinationCell = {2,2}

Output: 12
Explanation: One of the possible path can be below path: 
(0,1) → (0,0) → (1,0) → (2,0) → (2,1) → (1,1) → (1,2) → (0,2) → (0,3) → (1,3) → (2,3) → (2,2) 


 

Example 2: 
Input:  sourceCell = {1,1}      destinationCell = {2,2}

Output: 11
Explanation: One of the possible path can be below path: 
(1,1) → (1,2) → (1,3) → (0,3) → (0,2) → (0,1) → (0,0) → (1,0) → (2,0) → (2,1) → (2,2)

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

Approach 

We will solve this problem using backtracking and explore all the possible paths from the source to the destination cell. We will apply a depth-first search to explore all the possible paths: 

  1. To apply DFS Algorithm, explore all the possible 4 directions from the source cell and find the longest path from each adjacent cell. Mark the cell as visited for the current path on traversing a cell.
  2. After exploring all 4 directions, find the direction with the longest path and add 1 to that path (i.e., add the current cell to that path) to get the longest path from the current cell.
  3. After exploring all 4 directions, mark the current node as unvisited(backtrack).

Code in C++

#include<iostream>
#include<vector>
using namespace std;

int findLongestPath(
	int n,int m,
	vector<vector<bool> >& visited,
	int sourceRow,int sourceColumn,
	int destinationRow,int destinationColumn){

	if(sourceRow<0 || sourceColumn<0 || sourceRow>=n || sourceColumn>=m){
		return 0;
	}
	if(sourceRow==destinationRow && sourceColumn==destinationColumn){
		// since we are already at the destination, therefore longest path is of 1 size only
		return 1;
	}

	// Check if the current cell is already visited in the current path
	if(visited[sourceRow][sourceColumn]==true){
		return 0;
	}

	// mark the current cell visited for the further path
	visited[sourceRow][sourceColumn] = true;
	int longestPath = 1 + findLongestPath(n,m,visited,sourceRow+1,sourceColumn,destinationRow,destinationColumn);
	longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow-1,sourceColumn,destinationRow,destinationColumn));
	longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow,sourceColumn+1,destinationRow,destinationColumn));
	longestPath = max(longestPath,1 + findLongestPath(n,m,visited,sourceRow,sourceColumn-1,destinationRow,destinationColumn));

	// mark the current node as unvisited, so that it can be visited in some other path too
	visited[sourceRow][sourceColumn] = false;

	return longestPath;
}

int solve(vector<vector<int> >& matrix,vector<int> sourceCell,vector<int> destinationCell){
	int n = matrix.size();
	int m = matrix[0].size();

	// visited will help in maintaining the already visited nodes in the current path
	vector<vector<bool> > visited(n,vector<bool>(m,false));

	return findLongestPath(n,m,visited,sourceCell[0],sourceCell[1],destinationCell[0],destinationCell[1]);
}
int main(){
	vector<vector<int> > matrix{
		{5,4,1,0},
		{6,3,2,0},
		{7,8,9,0}
	};

	vector<int> sourceCell{0,1}, destinationCell{2,2};
	cout<<"Longest path from the source {0,1} to destination {2,2} is "<<solve(matrix,sourceCell,destinationCell)<<endl;

	sourceCell = {1,1};
	cout<<"Longest path from the source {1,1} to destination {2,2} is "<<solve(matrix,sourceCell,destinationCell)<<endl;
}

Output

Longest path from the source {0,1} to destination {2,2} is 12
Longest path from the source {1,1} to destination {2,2} is 11

Time Complexity

Since we will have 4 neighbors to explore for every cell, the time complexity is O(4(N*M)), where N = number of rows and M = number of columns in the matrix. 

Space Complexity

Since we are maintaining a visited matrix to check the already visited nodes in the current path, space complexity is O(N*M), where N = number of rows and M = number of columns in the matrix. 

Frequently Asked Questions

  1. What is the difference between a tree and a graph?
    Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
     
  2. What is the difference between a DFS Traversal and a BFS Traversal?
    In a DFS traversal of a graph, we begin from any random node and travel down each branch as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node at the current level before visiting their children nodes. 
    DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
     
  3. Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
    Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

This article taught us how to effectively use backtracking to determine the longest path from the source cell to the destination cell in a 2D matrix.

Since graphs are frequently asked in interviews, we recommend you practice more problems based on graphs on Coding Ninjas Studio. 

Recommended Problems:

Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!

Previous article
The K-th Lexicographical String of All Happy Strings of Length ‘N’
Next article
M Coloring Problem
Live masterclass