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

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â€ť.

#### 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.

Live masterclass