Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Example 1 
1.2.
Input
1.3.
Output: 
1.4.
Explanation: 
2.
Solution approach 
2.1.
Algorithm:
2.2.
 
2.3.
C++ Code implementation:
3.
Complexity Analysis
3.1.
Time complexity: O(N * M)
3.2.
Space complexity: O(N * M)
4.
FAQs
5.
Key Takeaways
Last Updated: Mar 27, 2024

Shortest path in a Matrix from top-left to bottom right-corner with neighbours exceeding at most K

Author Ayush Prakash
1 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

The problem statement is: Given a matrix M[][], and an integer K, we need to find the length of the shortest path from the top-left cell to the bottom-right cell of the matrix. The constraint is: the difference between the neighbouring elements must not exceed “K”.

Example 1 

Input

M[][] = 
{
	{1, 2, -19, 0},
	{2, 5, 6, -3},
	{11, 13, 5, 1},
	{8, 9, 10, 4}
}
K = 5

Output: 

6

Explanation: 

The shortest path following the given constraint is 1 -> 2 -> 5 -> 6 -> 5 -> 1 -> 4. The length of this path is 6. 

Solution approach 

Idea: The idea is pretty simple. We run a BFS where we enqueue the adjacent elements only when the difference between the current element and the adjacent element is <= K.

Algorithm:

  • Maintain a queue “Q” and a VISITED array, dimensions of which are equal to the given matrix. 
  • Insert the top-left node into the Q and mark VISITED[0][0] = true.
  • Now, while Q is not empty, do the following:
    • Pop from the Q. The node provides us with three pieces of information: 
      • Row index = i
      • Column index = j
      • Steps = length of the shortest path from (0,0) to (i, j)
    • Check if the node corresponds to the bottom left node, i.e. i==(R - 1) and j==(C-1), where R and C are the numbers of rows and columns, respectively. Suppose this is the case return Steps.
    • Else, iterate through all of its adjacent nodes (4-way connected) and do the following: 
      • Let us denote an adjacent cell by M[next_i][next_j]. If the cell lies within the boundaries of the matrix and it is not VISITED i.e. VISITED[next_i][next_j] = FALSE and | M[i][j] - M[next_i][next_j] | <= K then push the node {next_i, next_j, Steps + 1} into the Q and mark it as VISITED. Note we increased the number of Steps by 1. This signifies that this node may possibly be included in the shortest path. 
      • If (i) doesn’t hold, just skip. 
  • If anything is not returned in the above loop, just return -1. This means that there does not exist any path with the given constraints. 

 

C++ Code implementation:

​​#include <bits/stdc++.h>
using namespace std;
 
int shortestPath(vector<vector<int>> &m, int K)
{
  int r = m.size();

  // If the matrix is empty, return 0
  if (r == 0)
   {
      return 0;
   }

  int c = m[0].size();

  /*
  	 Declaring queue, this is the main data structure
  	 that help us to perform a BFS
  */
  queue<tuple<int, int, int>> q;

  /*
  	 The first value in the tuple: row index (i)
  	 The second value in the tuple: column index (j)
  	 The third value in the tuple: length of the shortest path from (0,0) to (i,j)
  */
 
  /*
  	 Declaring a visited array to hold the
  	 information of which nodes are already
  	 visited
  */
  vector<vector<bool>> visited(r, vector<bool>(c, false));
  q.push(make_tuple(0, 0, 0));
  visited[0][0] = true;
  int di[] = {1, -1, 0, 0};
  int dj[] = {0, 0, 1, -1};
 
  /*
   	 Run a conditional bfs, we only
   	 push an element in the queue if the difference
   	 doesn't exceed K
 */
  while (not q.empty())
  {

      // Extracting a node from the front of the queue
      auto [i, j, steps] = q.front();
      q.pop();

      /*
      	 If the node corresponds to the bottom-right cell
      	 we return steps, which is our answer
      */
      if (i == r - 1 and j == c - 1)
       {
          return steps;
       }
 
      // Iterate over the adjacent cells
      for (int p = 0; p < 4; p++)
      {
          int next_i = i + di[p];
          int next_j = j + dj[p];

          // Check if the cell lies within the boundaries of the matrix
          if (next_i >= 0 and next_i < r and next_j >= 0 and next_j < c)
          {

              /*
              	 Check if the node is already visited and the
              	 difference between the nodes in <= K
              */
              if (not visited[next_i][next_j] and abs(m[i][j] - m[next_i][next_j]) <= K)
              {
                  q.push(make_tuple(next_i, next_j, steps + 1));
                  visited[next_i][next_j] = true;
              }
          }
      }
  }

  // If there is no path possible, return -1
  return -1;
}
 
int main()
{
  vector<vector<int>> m{
      {1, 2, -19, 0},
      {2, 5, 6, -3},
      {11, 13, 5, 1},
      {8, 9, 10, 4}};
  cout << shortestPath(m, 5);
}

Output: 

6
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

Complexity Analysis

Time complexity: O(N * M)

Here, N and M is the number of rows and columns in the matrix. During BFS, we have to traverse every cell in the matrix in the worst case. Hence the time complexity is O(N * M).

Space complexity: O(N * M)

We are maintaining a N X M VISITED[][] array to keep track of the visited cells so that we don’t have to repeat any operations. Hence the space complexity is O(N*M).

FAQs

  1. Can the time or space complexity be improved?
    The time complexity can’t be improved but, the space complexity can be improved. Instead of using a VISITED[][] array, we could mark the cells which are already visited with some constant value (say, INT_MIN provided INT_MIN never occurs in the matrix). This is done in place, so the space complexity becomes O(1). 
     
  2. When to use BFS? 
    When source and destination are given, and you have to find the shortest path, and there may be other constraints as well, then there is a high chance that we could use BFS. 

Key Takeaways

In this blog, we solved a problem where we have to find the length of the shortest path in the matrix, from the top-left cell to the bottom-right, where the difference of the neighbouring elements must not exceed K. We used a very famous graph algorithm, BFS with slight modifications. We also analysed the time and space complexity of the approach. 

Check out this problem - Root To Leaf Path

Graph algorithms such as BFS, DFS Algorithm are asked a lot in coding interview rounds in various tech companies. To practice more of such algorithms, follow this incredible platform Coding Ninjas Studio.

If you like the article, please share it with your friends. Happy coding. 

Previous article
Shortest distance between two nodes in a Graph by reducing the weight of an edge by half
Next article
Minimum edges connected to node B to be removed from undirected graph to remove any existing path between nodes A and B.
Live masterclass