Table of Contents
Problem Statement
The problem “Distance of nearest cell having 1 in a binary matrix” states that you are given a binary matrix(containing only 0s and 1s) with at least one 1. Find the distance of the nearest cell having 1 in the binary matrix for all the elements of the matrix, here the distance between two cells (x1, y1) and (x2, y2) is |x2 – x1| + |y2 – y1|.
Examples
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}{
{1, 0, 1}
{1, 1, 2}
{0, 1, 2}
}Explanation: We can see that cells having 1 have 0 in the resultant matrix and cells at a distance of 1 from the cells having 1. These cells have 1 as output and similarly, distances have been calculated for other cells.
{
{0, 0, 0}
{0, 0, 0}
{1, 0, 1}
}{
{2, 3, 2}
{1, 2, 1}
{0, 1, 0}
}Naive Approach
For every element of the matrix, traverse the whole matrix and find the cell with least distance having 1 in the matrix.
- Create an array ans of size same as the array matrix. Run two nested loops to traverse all the elements of the matrix.
- For each element in the matrix, run two more nested loops to traverse each element of the matrix, let us can this as the current element. For all the current elements that are 1, find the minimum distance element and store that distance in the ans array.
- Print the ans array.
Complexity Analysis
Time Complexity = O(n2 * m2)
Space Complexity = O(n * m)
where n and m are the rows and columns of the given matrix respectively.
Since we are traversing the whole matrix for each of the cell in the matrix. This makes the algorithm to run in higher time complexity. Space complexity is just because of storing the output, but the algorithm itself requires constant space. If we would have simply printed the output, then this space complexity would have also been reduced.
Code
Java code to find Distance of nearest cell having 1 in a binary matrix
class DistanceOfNearestCellHaving1InABinaryMatrix {
private static void minimumDistance(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
int[][] ans = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int minDist = Integer.MAX_VALUE;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (matrix[x][y] == 1) {
int dist = Math.abs(x - i) + Math.abs(y - j);
minDist = Math.min(minDist, dist);
}
}
}
ans[i][j] = minDist;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(ans[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
int matrix1[][] = new int[][]{
{0, 1, 0},
{0, 0, 0},
{1, 0, 0}
};
minimumDistance(matrix1);
int matrix2[][] = new int[][]{
{0, 0, 0},
{0, 0, 0},
{1, 0, 1}
};
minimumDistance(matrix2);
}
}1 0 1 1 1 2 0 1 2 2 3 2 1 2 1 0 1 0
C++ Code to find Distance of nearest cell having 1 in a binary matrix
#include<bits/stdc++.h>
using namespace std;
void minimumDistance(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
int ans[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int minDist = INT_MAX;
for (int x = 0; x < n; x++) {
for (int y = 0; y < m; y++) {
if (matrix[x][y] == 1) {
int dist = abs(x - i) + abs(y - j);
minDist = std::min(minDist, dist);
}
}
}
ans[i][j] = minDist;
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int main() {
// Example 1
vector<vector<int>> matrix1 = {
{0, 1, 0},
{0, 0, 0},
{1, 0, 0}
};
minimumDistance(matrix1);
// Example 2
vector<vector<int>> matrix2 = {
{0, 0, 0},
{0, 0, 0},
{1, 0, 1}
};
minimumDistance(matrix2);
return 0;
}1 0 1 1 1 2 0 1 2 2 3 2 1 2 1 0 1 0
Optimal Approach
The better approach is to do a BFS starting from all the 1s in the given matrix. The distance of all the 1s is zero and for all the adjacent the minimum distance is one more than this.
- Create a queue of Coordinates, that is used to store the (row, column) of an element. Create an array ans of size same as array matrix.
- Traverse through all the elements of the matrix and push the coordinates of elements that are 1 into the queue.
- Initialize a variable minDistance as 0. While queue is not empty repeat steps 4 and 5.
- Initialize a variable size as size of the queue. Run a loop for i equals 0 to size(not included). At every iteration pop out an element from the queue. Set ans[row][col] as minDistance, and enqueue all the valid adjacents of this element that are 0 in the matrix array and set them as 1 in the matrix array.
- Increment minDistance.
- Print the ans array.
Complexity Anlaysis
Time Complexity = O(n * m)
Space Complexity = O(n * m)
where n and m are the rows and columns of the given matrix respectively.
The algorithm is very much similar to the BFS for graphs and thus only O(N*M) time has been taken.
Explanation
Consider the example,
{
{0, 1, 0}
{0, 0, 0}
{1, 0, 0}
}
Code
Java Code to find Distance of nearest cell having 1 in a binary matrix
import java.util.LinkedList;
import java.util.Queue;
class Optimal {
private static void minimumDistance(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;
// create an array ans of size same as matrix array
int ans[][] = new int[n][m];
// create a queue of coordinates
// push all the elements that are equals to 1 in the matrix array to the queue
Queue<Coordinate> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
queue.add(new Coordinate(i, j));
}
}
}
// initialize minDistance as 0
int minDistance = 0;
while (!queue.isEmpty()) {
// initialize size as size of queue
int size = queue.size();
// Run a loop size times
for (int i = 0; i < size; i++) {
// remove an element from queue
Coordinate curr = queue.poll();
// ans to this coordinate is minDistance
ans[curr.row][curr.col] = minDistance;
// enqueue all the valid adjacent cells of curr that are equals to
// 0 in the matrix array and set them as 1
// left adjacent
int leftRow = curr.row - 1;
int leftCol = curr.col;
if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
if (matrix[leftRow][leftCol] == 0) {
queue.add(new Coordinate(leftRow, leftCol));
matrix[leftRow][leftCol] = 1;
}
}
// right adjacent
int rightRow = curr.row + 1;
int rightCol = curr.col;
if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
if (matrix[rightRow][rightCol] == 0) {
queue.add(new Coordinate(rightRow, rightCol));
matrix[rightRow][rightCol] = 1;
}
}
// up adjacent
int upRow = curr.row;
int upCol = curr.col + 1;
if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
if (matrix[upRow][upCol] == 0) {
queue.add(new Coordinate(upRow, upCol));
matrix[upRow][upCol] = 1;
}
}
// down adjacent
int downRow = curr.row;
int downCol = curr.col - 1;
if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
if (matrix[downRow][downCol] == 0) {
queue.add(new Coordinate(downRow, downCol));
matrix[downRow][downCol] = 1;
}
}
}
// increment minimum distance
minDistance++;
}
// print the elements of the ans array
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
System.out.print(ans[i][j] + " ");
}
System.out.println();
}
System.out.println();
}
public static void main(String[] args) {
// Example 1
int matrix1[][] = new int[][]{
{0, 1, 0},
{0, 0, 0},
{1, 0, 0}
};
minimumDistance(matrix1);
// Example 2
int matrix2[][] = new int[][]{
{0, 0, 0},
{0, 0, 0},
{1, 0, 1}
};
minimumDistance(matrix2);
}
// class representing coordinates of a cell in matrix
static class Coordinate {
int row;
int col;
public Coordinate(int row, int col) {
this.row = row;
this.col = col;
}
}
}1 0 1 1 1 2 0 1 2 2 3 2 1 2 1 0 1 0
C++ Code to find Distance of nearest cell having 1 in a binary matrix
#include<bits/stdc++.h>
using namespace std;
// class representing coordinates of a cell in matrix
class Coordinate {
public:
int row;
int col;
Coordinate(int r, int c) {
row = r;
col = c;
}
};
void minimumDistance(vector<vector<int>> &matrix) {
int n = matrix.size();
int m = matrix[0].size();
// create an array ans of size same as matrix array
int ans[n][m];
// create a queue of coordinates
// push all the elements that are equals to 1 in the matrix array to the queue
queue<Coordinate> q;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (matrix[i][j] == 1) {
Coordinate coordinate(i, j);
q.push(coordinate);
}
}
}
// initialize minDistance as 0
int minDistance = 0;
while (!q.empty()) {
// initialize size as size of queue
int size = q.size();
// Run a loop size times
for (int i = 0; i < size; i++) {
// remove an element from queue
Coordinate curr = q.front();
q.pop();
// ans to this coordinate is minDistance
ans[curr.row][curr.col] = minDistance;
// enqueue all the valid adjacent cells of curr that are equals to
// 0 in the matrix array and set them as 1
// left adjacent
int leftRow = curr.row - 1;
int leftCol = curr.col;
if ((leftRow >= 0 && leftRow < n) && (leftCol >= 0 && leftCol < m)) {
if (matrix[leftRow][leftCol] == 0) {
Coordinate cLeft(leftRow, leftCol);
q.push(cLeft);
matrix[leftRow][leftCol] = 1;
}
}
// right adjacent
int rightRow = curr.row + 1;
int rightCol = curr.col;
if ((rightRow >= 0 && rightRow < n) && (rightCol >= 0 && rightCol < m)) {
if (matrix[rightRow][rightCol] == 0) {
Coordinate cRight(rightRow, rightCol);
q.push(cRight);
matrix[rightRow][rightCol] = 1;
}
}
// up adjacent
int upRow = curr.row;
int upCol = curr.col + 1;
if ((upRow >= 0 && upRow < n) && (upCol >= 0 && upCol < m)) {
if (matrix[upRow][upCol] == 0) {
Coordinate cUp(upRow, upCol);
q.push(cUp);
matrix[upRow][upCol] = 1;
}
}
// down adjacent
int downRow = curr.row;
int downCol = curr.col - 1;
if ((downRow >= 0 && downRow < n) && (downCol >= 0 && downCol < m)) {
if (matrix[downRow][downCol] == 0) {
Coordinate cDown(downRow, downCol);
q.push(cDown);
matrix[downRow][downCol] = 1;
}
}
}
// increment minimum distance
minDistance++;
}
// print the elements of the ans array
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout<<ans[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}
int main() {
// Example 1
vector<vector<int>> matrix1 = {
{0, 1, 0},
{0, 0, 0},
{1, 0, 0}
};
minimumDistance(matrix1);
// Example 2
vector<vector<int>> matrix2 = {
{0, 0, 0},
{0, 0, 0},
{1, 0, 1}
};
minimumDistance(matrix2);
return 0;
}1 0 1 1 1 2 0 1 2 2 3 2 1 2 1 0 1 0