Welcome to Subscribe On Youtube
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:
- The number of elements of the given matrix will not exceed 10,000.
- There are at least one 0 in the given matrix.
- 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; } }
-
// OJ: https://leetcode.com/problems/01-matrix/ // Time: O(MN) // Space: O(MN) class Solution { public: vector<vector<int>> updateMatrix(vector<vector<int>>& A) { int M = A.size(), N = A[0].size(), step = 1, dirs[4][2] = { {0,1},{0,-1},{1,0},{-1,0} }; vector<vector<int>> ans(M, vector<int>(N, INT_MAX)); queue<pair<int, int>> q; for (int i = 0; i < M; ++i) { for (int j = 0; j < N; ++j) { if (A[i][j] == 0) { q.emplace(i, j); ans[i][j] = 0; } } } while (q.size()) { int cnt = q.size(); while (cnt--) { auto [x, y] = q.front(); q.pop(); for (auto &[dx, dy] : dirs) { int a = x + dx, b = y + dy; if (a < 0 || a >= M || b < 0 || b >= N || ans[a][b] != INT_MAX) continue; q.emplace(a, b); ans[a][b] = step; } } ++step; } return ans; } };
-
class Solution: def updateMatrix(self, mat: List[List[int]]) -> List[List[int]]: m, n = len(mat), len(mat[0]) ans = [[-1] * n for _ in range(m)] q = deque() for i in range(m): for j in range(n): if mat[i][j] == 0: ans[i][j] = 0 q.append((i, j)) dirs = [(0, 1), (0, -1), (1, 0), (-1, 0)] while q: i, j = q.popleft() for a, b in dirs: x, y = i + a, j + b if 0 <= x < m and 0 <= y < n and ans[x][y] == -1: ans[x][y] = ans[i][j] + 1 q.append((x, y)) return ans ############ from collections import deque class Solution(object): def updateMatrix(self, matrix): """ :type matrix: List[List[int]] :rtype: List[List[int]] """ queue = deque([]) directions = [(0, -1), (0, 1), (-1, 0), (1, 0)] for i in range(len(matrix)): for j in range(len(matrix[0])): if matrix[i][j] == 0: queue.append((i, j)) if matrix[i][j] == 1: matrix[i][j] = -1 while queue: i, j = queue.popleft() for di, dj in directions: ni, nj = i + di, j + dj if 0 <= ni < len(matrix) and 0 <= nj < len(matrix[0]) and matrix[ni][nj] == -1: matrix[ni][nj] = matrix[i][j] + 1 queue.append((ni, nj)) return matrix
-
func updateMatrix(mat [][]int) [][]int { m, n := len(mat), len(mat[0]) ans := make([][]int, m) for i := range ans { ans[i] = make([]int, n) for j := range ans[i] { ans[i][j] = -1 } } type pair struct{ x, y int } var q []pair for i, row := range mat { for j, v := range row { if v == 0 { ans[i][j] = 0 q = append(q, pair{i, j}) } } } dirs := []int{-1, 0, 1, 0, -1} for len(q) > 0 { p := q[0] q = q[1:] for i := 0; i < 4; i++ { x, y := p.x+dirs[i], p.y+dirs[i+1] if x >= 0 && x < m && y >= 0 && y < n && ans[x][y] == -1 { ans[x][y] = ans[p.x][p.y] + 1 q = append(q, pair{x, y}) } } } return ans }
-
use std::collections::VecDeque; impl Solution { #[allow(dead_code)] pub fn update_matrix(mat: Vec<Vec<i32>>) -> Vec<Vec<i32>> { let n: usize = mat.len(); let m: usize = mat[0].len(); let mut ret_vec: Vec<Vec<i32>> = vec![vec![-1; m]; n]; // The inner tuple is of <X, Y, Current Count> let mut the_q: VecDeque<(usize, usize)> = VecDeque::new(); let traverse_vec: Vec<(i32, i32)> = vec![(-1, 0), (1, 0), (0, 1), (0, -1)]; // Initialize the queue for i in 0..n { for j in 0..m { if mat[i][j] == 0 { // For the zero cell, enqueue at first the_q.push_back((i, j)); // Set to 0 in return vector ret_vec[i][j] = 0; } } } while !the_q.is_empty() { let (x, y) = the_q.front().unwrap().clone(); the_q.pop_front(); for pair in &traverse_vec { let cur_x = pair.0 + x as i32; let cur_y = pair.1 + y as i32; if Solution::check_bounds(cur_x, cur_y, n as i32, m as i32) && ret_vec[cur_x as usize][cur_y as usize] == -1 { // The current cell has not be updated yet, and is also in bound ret_vec[cur_x as usize][cur_y as usize] = ret_vec[x][y] + 1; the_q.push_back((cur_x as usize, cur_y as usize)); } } } ret_vec } #[allow(dead_code)] pub fn check_bounds(i: i32, j: i32, n: i32, m: i32) -> bool { i >= 0 && i < n && j >= 0 && j < m } }
-
function updateMatrix(mat: number[][]): number[][] { const [m, n] = [mat.length, mat[0].length]; const ans: number[][] = Array.from({ length: m }, () => Array.from({ length: n }, () => -1)); const q: [number, number][] = []; for (let i = 0; i < m; ++i) { for (let j = 0; j < n; ++j) { if (mat[i][j] === 0) { q.push([i, j]); ans[i][j] = 0; } } } const dirs: number[] = [-1, 0, 1, 0, -1]; while (q.length) { const [i, j] = q.shift()!; for (let k = 0; k < 4; ++k) { const [x, y] = [i + dirs[k], j + dirs[k + 1]]; if (x >= 0 && x < m && y >= 0 && y < n && ans[x][y] === -1) { ans[x][y] = ans[i][j] + 1; q.push([x, y]); } } } return ans; }