Home » Technical Interview Questions » Queue Interview Questions » Distance of nearest cell having 1 in a binary matrix

Distance of nearest cell having 1 in a binary matrix


Reading Time - 10 mins


Difficulty Level Easy

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.

  1. Create an array ans of size same as the array matrix. Run two nested loops to traverse all the elements of the matrix.
  2. 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.
  3. 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.

  1. 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.
  2. Traverse through all the elements of the matrix and push the coordinates of elements that are 1 into the queue.
  3. Initialize a variable minDistance as 0. While queue is not empty repeat steps 4 and 5.
  4. 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.
  5. Increment minDistance.
  6. Print the ans array.
READ  Reversing the First K elements of a Queue

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}
}

Distance of nearest cell having 1 in a binary matrix

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
Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions