Formatted question description: https://leetcode.ca/all/542.html

542. 01 Matrix

Level

Medium

Description

Given a matrix consists of 0 and 1, find the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example 1:

Input:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Output:
[[0,0,0],
 [0,1,0],
 [0,0,0]]

Example 2:

Input:
[[0,0,0],
 [0,1,0],
 [1,1,1]]

Output:
[[0,0,0],
 [0,1,0],
 [1,2,1]]

Note:

  1. The number of elements of the given matrix will not exceed 10,000.
  2. There are at least one 0 in the given matrix.
  3. The cells are adjacent in only four directions: up, down, left and right.

Solution

Use breadth first search. Offer all the cells with value 0 to the queue, and initialize the distances of all the cells with value 1 to Integer.MAX_VALUE. Starting from each cell with value 0, update its adjacent cells’ distances. If an adjacent cell has value 0, then the distance of the adjacent cell is 0. If an adjacent cell has value 1, then the distance of the adjacent cell is updated using the shortest distance.

class Solution {
    public int[][] updateMatrix(int[][] matrix) {
        int rows = matrix.length, columns = matrix[0].length;
        int[][] distances = new int[rows][columns];
        Queue<int[]> queue = new LinkedList<int[]>();
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < columns; j++) {
                if (matrix[i][j] == 0)
                    queue.offer(new int[]{i, j});
                else
                    distances[i][j] = Integer.MAX_VALUE;
            }
        }
        int[][] directions = { {-1, 0}, {1, 0}, {0, -1}, {0, 1} };
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int row = cell[0], column = cell[1];
            int distance = distances[row][column];
            int newDistance = distance + 1;
            for (int[] direction : directions) {
                int newRow = row + direction[0], newColumn = column + direction[1];
                if (newRow >= 0 && newRow < rows && newColumn >= 0 && newColumn < columns) {
                    if (distances[newRow][newColumn] > newDistance) {
                        distances[newRow][newColumn] = newDistance;
                        queue.offer(new int[]{newRow, newColumn});
                    }
                }
            }
        }
        return distances;
    }
}

All Problems

All Solutions