01 matrix

XXX. Update Matrix

BFS

Matrix

Problem Statement:

Given an m x n binary matrix mat, return a matrix result such that for each cell result[i][j], it contains the distance to the nearest 0 in mat. The distance between two adjacent cells is 1.

Approach:

1. Initialize a queue and a seen array to keep track of visited cells.
2. Enqueue all cells with a value of 0, as these are the starting points for the BFS.
3. Perform a Breadth-First Search (BFS) from all 0 cells simultaneously:
   • For each cell, explore its neighbors in four directions (up, down, left, right).
   • If a neighbor hasn't been visited, update its distance in the result matrix and mark it as visited.
   • Enqueue the neighbor for further exploration.
4. Continue until all cells have been processed.

Java Implementation:

class State {
    int row;
    int col;
    int steps;

    // Constructor to store state information: row, column, and distance (steps)
    State(int row, int col, int steps) {
        this.row = row;
        this.col = col;
        this.steps = steps;
    }
}

class Solution {
    int m, n; // Dimensions of the matrix
    int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}}; // Movement directions: right, down, left, up

    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        int[][] matrix = new int[m][n]; // Result matrix
        boolean[][] seen = new boolean[m][n]; // Tracks visited cells
        Queue queue = new LinkedList<>(); // BFS queue

        // Step 1: Enqueue all cells with 0 and mark them as seen
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                if (mat[row][col] == 0) {
                    queue.add(new State(row, col, 0));
                    seen[row][col] = true;
                }
            }
        }

        // Step 2: BFS to calculate distances
        while (!queue.isEmpty()) {
            State state = queue.poll();
            int row = state.row, col = state.col, steps = state.steps;

            // Explore neighbors
            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];
                if (valid(nextRow, nextCol) && !seen[nextRow][nextCol]) {
                    seen[nextRow][nextCol] = true; // Mark as visited
                    queue.add(new State(nextRow, nextCol, steps + 1));
                    matrix[nextRow][nextCol] = steps + 1; // Update distance
                }
            }
        }

        return matrix;
    }

    // Helper method to validate cell boundaries
    public boolean valid(int row, int col) {
        return 0 <= row && row < m && 0 <= col && col < n;
    }
}
        

Key Insights:

• Multi-source BFS: By enqueuing all 0 cells first, we start the BFS from multiple sources simultaneously.
• Directional Traversal: Use the directions array to easily explore all possible neighbors.
• Visited Tracking: The seen array ensures each cell is processed only once, optimizing the solution.

Complexity Analysis:

Time Complexity: O(m * n), where m is the number of rows and n is the number of columns, as each cell is processed once.
Space Complexity: O(m * n), due to the queue and the seen array.