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
2 upvotes
Career growth poll
Do you think IIT Guwahati certified course can help you in your career?

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);
}
You can also try this code with Online C++ Compiler
Run Code

Output: 

6

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. 

Live masterclass