LeetCode 542: 01 Matrix Solution

Master LeetCode problem 542 (01 Matrix), a medium challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

542. 01 Matrix

Medium

Array Dynamic Programming Breadth-First Search Matrix

Problem Explanation

Explanation

To solve this problem, we can use a breadth-first search (BFS) approach. We start by initializing a queue with all cells that have the value 0. Then, we iterate through the queue, popping cells one by one and updating their neighboring cells with the distance from the original cell. We continue this process until all cells are visited. At the end, the distances stored in the matrix will represent the distance of the nearest 0 for each cell.

Time complexity: O(m * n) where m is the number of rows and n is the number of columns in the matrix. Space complexity: O(m * n) for the queue and the resulting matrix.

Solution Code

import java.util.LinkedList;
import java.util.Queue;

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;

        Queue<int[]> queue = new LinkedList<>();
        int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (mat[i][j] == 0) {
                    queue.offer(new int[]{i, j});
                } else {
                    mat[i][j] = Integer.MAX_VALUE;
                }
            }
        }

        while (!queue.isEmpty()) {
            int[] curr = queue.poll();
            int row = curr[0];
            int col = curr[1];

            for (int[] dir : directions) {
                int newRow = row + dir[0];
                int newCol = col + dir[1];

                if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || mat[newRow][newCol] <= mat[row][col] + 1) {
                    continue;
                }

                mat[newRow][newCol] = mat[row][col] + 1;
                queue.offer(new int[]{newRow, newCol});
            }
        }

        return mat;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 542 (01 Matrix)?

This page provides optimized solutions for LeetCode problem 542 (01 Matrix) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 542 (01 Matrix)?

The time complexity for LeetCode 542 (01 Matrix) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 542 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 542 in Java, C++, or Python.

Back to LeetCode Solutions