Maximum 0-1 Distance

Hard
0/120
Average time to solve is 10m
profile
Contributed by
4 upvotes
Asked in company
Amazon

Problem statement

You are given an N*M binary matrix, considering for every 0-cell(cell with value = 0) the distance from this cell to its nearest 1-cell(cell with value = 1) is 'di', you need to find the maximum value of 'di' among all values of 'di'. Formally, if the minimum distance from an 'ith' 0-cell to any 1-cell is ‘di’, you need to find max(di), where i belongs to the set of all 0-cells in the matrix.

Distance between cells (i,j) and (a,b) is given as (|i-a| + |j-b|) i.e the manhattan distance is considered here.

altImage

Here, the arrows starting from the 0-cell’s point towards their corresponding nearest one cell, and among all of these, the arrow in purple and orange gives the maximum distance, i.e., 2.

Note:

1) Binary matrix of size N*M is a matrix with N rows and M columns, in which all the cells have either value 0 or 1.
2) Nearest 1-cell from a 0-cell is the cell that contains 1 and is at least a distance from the 0-cell being considered among all the other cells. For example consider the matrix {{0,1},{0,1}}. Here the nearest 1-cell for the 0-cell at index(0,0) is the 1-cell at index (0,1) because this cell is at least distance from the 0-cell being considered as the distance from the other 1-cell at index(1,1) is 2, whereas the distance from the 1-cell at index (0,1) is 1.
3) If there are no 1-cells or no 0-cells in the matrix, return -1.
Detailed explanation ( Input/output format, Notes, Images )
Input Format: 
The first line of the input contains an integer 'T' denoting the number of test cases. Then 'T' test cases follow:

The first line of each test case contains two space-separated integers, 'N' and 'M', where 'N'  is the number of rows in the given matrix and 'M' is the number of columns in the given matrix.

Then 'N' lines follow for each test case:

Each line contains 'M' space-separated integers(either 1 or 0).

For more clarity, please refer to the sample input.
Output Format: 
Each test case's the only line of output consists of an integer 'X', denoting the maximum possible distance from a 0-cell to its nearest 1-cell.

Output for each test case will be printed in a separate line.
Note: 
You do not need to print anything, and it has already been taken care of. Just implement the given function.
Constraints: 
1 <= T <= 100
1 <= N <= 100
1 <= M <= 100

where 'T' is the number of test cases, 'N' is the number of rows in the given matrix, and 'M' is the number of columns in the given matrix.
Time Limit: 1 sec.
Sample Input 1:
1
2 2
0 1
0 0
Sample Output 1:
2
Explanation for sample input 1:
The 0-cells are at positions (0,0), (1,0), and (1,1) respectively. 
The 1-cell nearest to the 0-cell at position (0,0) is at (0,1), distance=1.
The 1-cell nearest to the 0-cell at position (1,0) is at (0,1), distance=2.
The 1-cell nearest to the 0-cell at position (1,1) is at (0,1), distance=1.
So, the maximum of all distances is 2, which is the answer in our case.
Sample Input 2:
1
3 3
0 0 1
0 1 0
0 0 0
Sample Output 2:
2
Explanation for sample input 2:
The 1-cell at (1,1) is nearest to the 0-cell at (2,0), giving us the maximum distance.
Hint

Find all the valid distances and then take the maximum.

Approaches (2)
Brute Force
  • Before starting with the main algorithm, let's look at the conditions when the answer will be -1. There are only two such conditions:
  1. If all the cells are 1-cell, then, in this case, return -1 as the answer.
  2. If all the cells are 0-cell, then also return -1 as the answer.
  • Our problem is to find the maximum distance from a 0-cell to the nearest 1-cell, so what we can do is store the positions of all the 1-cells in a vector of pairs by iterating through the matrix.
  • Initialize variable answer to 0 before proceeding further.
  • Now once again, iterate through each cell of the matrix. If the cell being traversed has a value of 1, then skip that cell, but if the value of the cell being traversed is 0, then run a nested loop and calculate the distance of this 0-cell from all the 1-cells stored in the vector before and get the minimum distance. Now this distance will be the distance from the 0-cell being traversed and its nearest 1-cell.
  • Since we have to calculate the maximum of all such distances, Thus after finding the nearest distance for any 0-cell update answer as answer = max(answer, nearest distance found).
  • After completing the above steps, return the answer because it will contain the max distance between a 0-cell and its nearest 1-cell.
Time Complexity

O(N*M*P), where ‘N’ is the number of rows, ‘M’ is the number of columns, and ‘P’ is the number of 1-cells in the given binary matrix.

Space Complexity

O(P), where ‘P’ is the number of 1-cells in the given binary matrix.

Code Solution
(100% EXP penalty)
Maximum 0-1 Distance
Full screen
Console