Last Updated: 18 Mar, 2021

Binary Matrix

Hard

Asked in companies

Solve now

Problem statement

You are given a matrix ‘MAT’ consisting of ‘N’ rows and ‘M’ columns. Let (i, j) represent the cell at the intersection of the ith row and the jth column. Each cell of the matrix ‘MAT’ has either integer 0 or 1. For each cell in ‘MAT’, you have to find the Manhattan distance of the nearest cell from this cell that has the integer 0. The nearest cell will be the cell having the minimum Manhattan distance from it.

Manhattan distance between two cells, (p1, q1) and (p2, q2) is |p1 - p2| + |q1 - q2|.

You should return a matrix consisting of ‘N’ rows and ‘M’ columns, where the cell (i, j) represents the Manhattan distance of the nearest cell from the cell (i, j) in ‘MAT’ that has integer 0.

Note

1. There is at least one cell having the integer 0 in the given matrix.

Example:

Consider the following 2*3 matrix ‘MAT’:
                 [0, 1, 1]
                 [0, 1, 1]

Here, the nearest cell having the integer 0 from the cell (0, 0) is the cell (0, 0) itself. The Manhattan distance between them is |0 - 0| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (0, 1) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (0, 2) is cell (0, 0). The Manhattan distance between them is |0 - 0| + |2 - 0| = 2.

The nearest cell having the integer 0 from the cell (1, 0) is cell (1, 0) itself. The Manhattan distance between them is |1 - 1| + |0 - 0| = 0.

The nearest cell having the integer 0 from the cell (1, 1) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |1 - 0| = 1.

The nearest cell having the integer 0 from the cell (1, 2) is cell (1, 0). The Manhattan distance between them is |1 - 1| + |2 - 0| = 2.
Thus we should return matrix:

                [0, 1, 2]
                [0, 1, 2]

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases. then ‘T’ test cases follow.

The first line of each test case consists of two single space-separated integers ‘N’ and ‘M’ representing the number of rows and columns in matrix ‘MAT’

Then next ‘N’ lines follow in each test case. Each of these ‘N’ lines consists of ‘M’ single space-separated integers (either 0 or 1).  These ‘N’ lines together represent the matrix ‘MAT’.

Output format :

For each test case, print ‘N’ lines each of which consists of ‘M’ space-separated integers. The jth integer in the ith line will be the Manhattan distance of the nearest cell from the cell (i, j) in  ‘MAT’ that has integer 0.

The output of each test case will be printed in a separate line.

Note:

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

Constraints:

1 <= T <= 50
1 <= N <= 100
1 <= M <= 100
0 <= MAT[i][j] <= 1


Where ‘T’ is the total number of test cases,  ‘N’ and ‘M’ denote the number of rows and columns in the given matrix ‘MAT’, and MAT[i][j] is the element of the given matrix at cell (i, j). 

Time limit: 1 sec.

Solve now

Approaches

01 Approach

This approach is straightforward, we will make a matrix ‘DIST’ of dimension N * M and initially fill it with infinity. Then we iterate over each cell of the matrix ‘MAT’ and if we find any cell in ‘MAT’ that has integer 0, then we update the value of each cell in matrix ‘DIST’ with the minimum of its current value and its Manhattan distance from the current cell of ‘MAT’.

Algorithm

Create a matrix ‘DIST’ of dimension N * M and fill it with infinity.
Run a loop where ‘i’ ranges from 0 to ‘N’ - 1.
- Run a loop where ‘j’ ranges from 0 to ‘M’ - 1.
  - If ‘MAT[i][j]’ = 0, then run a nested loop where ‘k’ ranges from 0 to ‘N’-1 and for each ‘k’, ‘l’ ranges from 0 to ‘M’-1. for each ‘k’, ‘l’ do ‘DIST[k][l]’ = min(‘DIST[k][l]’, |i-k| + |j-l|) where |x| is the absolute value of ‘x’.
Return ‘DIST’.

Solve now

02 Approach

Let consider each cell of the matrix as a graph node. The node representing cell (i, j) is connected to the nodes representing its adjacent cells, i.e cell (i - 1, j), (i, j - 1), (i, j + 1), (i + 1, j).

Now we iterate over the matrix ‘MAT’ and find all the cells that have integer 0 and then we push all these cells in the queue and run the breadth-first search algorithm in a way described below.

Algorithm

Create a matrix ‘DIST’ of dimension N * M and fill it with infinity.
Create an empty queue of list/array of size 2.
Iterate over the given matrix ‘MAT’ and for each cell (i, j) if ‘MAT[i][j]’ = 0, then push cell (i, j) as list/arr [i, j] in the queue and do DIST[i][j]:= 0.
Run a while loop till the queue is not empty and in each iteration do the following:
- Let cell (x, y) be the front element of the queue.
- Dequeue the front element of the queue.
- Iterate over adjacent cells of (x, y) i.e cell (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y) (if exist) and for each adjacent cell (i, j) if ‘DIST[i][j]’ != infinity, then do ‘DIST[i][j]’ = ‘DIST[x][y]’ + 1 and push cell (i, j) in the queue.
Return ‘DIST’.

Solve now

03 Approach

Let ‘DIST[i][j]’ will be the Manhattan distance of each cell from the nearest cell that have integer 0, then -:

‘DIST[i][j]’ = 0 if cell (i, j) has integer 0.

Otherwise, ‘DIST[i][j]’ = min(‘DIST[i - 1][j]’, DIST[i][j - 1], DIST[i][j + 1], DIST[i + 1][j]) + 1.

We can compute this distance for each cell by iterating over ‘MAT’ two times, one by starting from the top left, and the other by starting from the bottom right cell as follows.

Algorithm

Create a matrix ‘DIST’ of dimension N * M and fill it with infinity.
Run a loop where ‘i’ ranges from 0 to ‘N’ - 1.
Run a loop where ‘j’ ranges from 0 to ‘M’ - 1.
If ‘MAT[i][j]’ = 0, then do ‘DIST[i][j]’: = 0.
Otherwise do DIST[i][j] = min(DIST[i - 1][j], DIST[i][j - 1]) + 1 (You may need to handle cases when (i - 1, j) or (i, j - 1) do not exist).
Run a loop where ‘i’ ranges from ‘N’ - 1 to 0.
Run a loop where ‘j’ ranges from ‘M - 1’ to 0.
Do DIST[i][j] = min(DIST[i][j], min(DIST[i + 1][j], DIST[i][j + 1]) + 1). (You may need to handle cases when (i+1, j) or (i, j+1) do not exist).
Return ‘DIST’.

Solve now

Binary Matrix

Problem statement

Manhattan distance between two cells, (p1, q1) and (p2, q2) is |p1 - p2| + |q1 - q2|.

You should return a matrix consisting of ‘N’ rows and ‘M’ columns, where the cell (i, j) represents the Manhattan distance of the nearest cell from the cell (i, j) in ‘MAT’ that has integer 0.

Note

Example:

Input format:

Output format :

Note:

Constraints:

Approaches

01 Approach

Algorithm

02 Approach

Algorithm

03 Approach

‘DIST[i][j]’ = 0 if cell (i, j) has integer 0. Otherwise, ‘DIST[i][j]’ = min(‘DIST[i - 1][j]’, DIST[i][j - 1], DIST[i][j + 1], DIST[i + 1][j]) + 1.

Algorithm

‘DIST[i][j]’ = 0 if cell (i, j) has integer 0.

Otherwise, ‘DIST[i][j]’ = min(‘DIST[i - 1][j]’, DIST[i][j - 1], DIST[i][j + 1], DIST[i + 1][j]) + 1.