Distance Of Nearest Cell Having 1 In A Binary Matrix

Moderate

0/80

Average time to solve is 35m

Contributed by

33 upvotes

Asked in companies

Problem statement

You have been given a binary matrix 'MAT' containing only 0’s and 1’s of size N x M. You need to find the distance of the nearest cell having 1 in the matrix for each cell.

The distance is calculated as |i1 – i2| + |j1 – j2|, where i1, j1 are the coordinates of the current cell and i2, j2 are the coordinates of the nearest cell having value 1.

Note :

You can only move in four directions which are : Up, Down, Left and Right.

For example :

If N = 3, M = 4

and mat[ ][ ] = { 0, 0, 0, 1,
                  0, 0, 1, 1,
                  0, 1, 1, 0 }

then the output matrix will be

3  2  1  0
2  1  0  0
1  0  0  1

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases are as follows.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ which denotes the size of the matrix.

The ‘N’ lines of each test case contain ‘M’ space-separated elements of the matrix.

Output Format:

For each test case, print a matrix of the same size containing the distance of the nearest cell having ‘1’ for each cell.

Note:

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

Constraints:

1 <= T <= 5
1 <= N <= 2*10^2
1 <= M <= 2*10^2

Where ‘T’ is the number of test cases, ‘N’ is the number of rows in the matrix and ‘M’ is the number of columns in the matrix.

Sample Input 1:

Sample Output 1:

3 2 1 0
2 1 0 0
1 0 0 1

Sample Input 2:

Sample Output 2:

0 1 1 
1 1 0 
1 0 0

Hint 1

Hint 2

Can you think of traversing each cell and finding the nearest cell having 1?

Approaches (2)

Approach 1

Approach 2

Brute Force

Traverse the matrix for all N*M cells one by one.
For every cell find the closest cell which contains 1.
Update the minimum distance.
Fill the minimum distance in the matrix.

Time Complexity

O(N^2 * M^2), where ‘N’ is the number of rows and ‘M’ is the number of columns of the matrix.

For every cell, all N*M cells are traversed.And there are a total of N*M cells in the matrix. So the overall time complexity will be O(N^2 * M^2).

Space Complexity

O(1).

Constant extra space required.

(100% EXP penalty)

Distance Of Nearest Cell Having 1 In A Binary Matrix

Console