Shortest Path in a Binary Matrix
You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing. 2. You can move in 4 directions (Up, Down, Left, Right) from a cell. 3. The length of the path is the number of 1s lying in the path. 4. The source cell is always filled with 1.

For example -

1 0 1 1 1 1 1 1 1 For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are X 0 X X 0 X X X X X 1 X 1 1 1 X X X The length of the shortest path is 5.

Input Format:

The first line of input contains two integers 'N' and 'M' separated by a single space representing the number of rows and columns in the binary matrix respectively. The next 'N' lines of the input contain 'M' single space-separated integers each representing the 'i'-th row of the Binary Matrix. The next line of input contains two single space-separated integers 'SOURCEX' and 'SOURCEY' representing the coordinates of the source cell. The next line of input contains two single space-separated integers 'DESTX' and 'DESTY' representing the coordinates of the destination cell.

Constraints :

1

Question

Shortest Path in a Binary Matrix

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

1. Coordinates of the cells are given in 0-based indexing.
2. You can move in 4 directions (Up, Down, Left, Right) from a cell.
3. The length of the path is the number of 1s lying in the path.
4. The source cell is always filled with 1.

For example -

1 0 1
1 1 1
1 1 1
For the given binary matrix and source cell(0,0) and destination cell(0,2). Few valid paths consisting of only 1s are

X 0 X     X 0 X 
X X X     X 1 X 
1 1 1     X X X 
The length of the shortest path is 5.

Input Format:

The first line of input contains two integers 'N' and 'M' separated by a single space representing the number of rows and columns in the binary matrix respectively.

The next 'N' lines of the input contain 'M' single space-separated integers each representing the 'i'-th row of the Binary Matrix.

The next line of input contains two single space-separated integers 'SOURCEX' and 'SOURCEY' representing the coordinates of the source cell.

The next line of input contains two single space-separated integers 'DESTX' and 'DESTY' representing the coordinates of the destination cell.

Constraints :

1 <= N <= 500
1 <= M <= 500
MAT[i] = {0, 1}

0 <= SOURCEX <= N - 1
0 <= SOURCEY <= M - 1
0 <= DESTX <= N - 1
0 <= DESTY <= M - 1
MAT[SOURCEX][SOURCEY] = 1

Time Limit: 1 sec

Output Format :

For each test case, print a single line that contains a single integer i.e. length of the shortest path from the source cell to the destination cell.

Note:

You do not need to print anything; it has already been taken care of. Just implement the given function.

Accepted Answer

1. Initialize distances of all vertices as infinite.
2. Create an empty priority_queue pq. Every item of pq is a pair (weight, vertex). Weight (or distance) is used as the first item of pair as the first item is by default used to compare two pairs
3. Insert source vertex into pq and make its distance as 0. While either pq doesn't become empty
a) Extract minimum distance vertex from pq. Let the extracted vertex be u.
b) Loop through all adjacent of u and do following for every vertex v.
If there is a shorter path to v through u.
If dist[v] > dist[u] + weight(u, v)
(i) Update distance of v, i.e., do dist[v] = dist[u] + weight(u, v)
(ii) Insert v into the pq (Even if v is already there)

Accepted Answer

Backtracking

To find the shortest path in the Binary Matrix, we search for all possible paths in the Binary Matrix from the source cell to the destination cell until all possibilities are exhausted. We can easily achieve this with the help of backtracking.

We start from the given source cell in the matrix and explore all four paths possible and recursively check if they will lead to the destination or not. Out of all those possible paths, we will pick the minimum length path from source to destination. If a path doesn't reach the destination cell or we have explored all possible routes from the current cell, we backtrack.

To make sure that the path is simple and doesn't contain any cycles, we keep track of cells involved in the current path in a boolean matrix ‘VISITED‘, and before exploring any cell, we ignore the cell if it is already covered in the current path.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.

We are using a boolean matrix to mark the visited cells. Hence, the space complexity is O(N * M).

Time Complexity: OtherExplanation:

O(4 ^ ( N * M )), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.

In the worst case, we can have all the elements as 1 in the Binary Matrix and have to explore all the cells. From every cell, we can move to 4 possible cells adjacent to it. Hence, the time complexity is O(4 ^ ( N * M)).

Accepted Answer

Breadth-First-Search

Before moving onto the BFS solution, we must know why Depth-First-Search doesn’t work in finding the shortest path. Here is a complete discussion on this topic.

Breadth-First-Search considers all the paths starting from the source and moves ahead one unit in all those paths at the same time. This makes sure that the first time when the destination is visited, it is the path with the shortest length.

Here, is the complete algorithm-

Create an empty queue and enqueue source cell and mark it as visited
Declare a ‘STEPS’ variable, to keep track of the length of the path so far
Loop in level order till the queue is not empty
- Fetch the front cell from the queue
- If the fetched cell is the destination cell, return ‘STEPS’
- Else for each of the 4 adjacent cells of the current cell, we enqueue each valid cell into the queue and mark them visited.
- Increment ‘STEPS’ by 1 when all the cells in the current level are processed.
If all nodes in the queue are processed and the destination cell is not reached, we return -1.

Space Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.

Since we are using extra space to process the elements of Matrix.

Time Complexity: O(m*n) - For 2d arraysExplanation:

O(N * M), where ‘N’ and ‘M’ are the number of rows and columns in the Binary Matrix respectively.

In the worst case, we can have all the elements as 1 in the Binary Matrix and have to explore all the cells. Since every node is visited at most one time, the time complexity is O(N * M).

You have been given a binary matrix of size 'N' * 'M' where each element is either 0 or 1. You are also given a source and a destination cell, both of them lie within the matrix.

Your task is to find the length of the shortest path from the source cell to the destination cell only consisting of 1s. If there is no path from source to destination cell, return -1.

Note:

For example -

Input Format:

Constraints :

Output Format :

Note:

Top SPRINKLR Production Analyst interview questions & answers

Popular interview questions of Production Analyst

Top HR questions asked in SPRINKLR Production Analyst