[LeetCode] 01 Matrix

Problem: Given an m x n binary matrix mat, return the distance of the nearest 0 for each cell.

The distance between two adjacent cells is 1.

Example:

Input: mat = [[0,0,0],[0,1,0],[0,0,0]]
Output: [[0,0,0],[0,1,0],[0,0,0]]

Input: mat = [[0,0,0],[0,1,0],[1,1,1]]
Output: [[0,0,0],[0,1,0],[1,2,1]]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• There is at least one 0 in mat.

Approach: This problem is getting the minimum distance between nodes of a graph. A node (cell) is connected to other node (cell) in case they are neighbours (left, right, up, down). Now we just need to calculate the minimum distance of cells with 0 to cells with 1. 

Given we need to calculate minimum distance, we need to apply the BFS here. That's all!

Implementation in C#:

    public int[][] UpdateMatrix(int[][] mat) 

    {

        int rows = mat?.Length ?? 0;

        if (rows == 0)

        {

            return new int[][]{};     

        }

        int cols = mat[0].Length;

        bool[,] visited = new bool[rows, cols];        

        Queue<int[]> queue = new Queue<int[]>();

        this.AddZeroCellsToQueue(mat, queue, visited);

        while (queue.Count != 0)

        {

            int[] cell = queue.Dequeue();

            this.UpdateNeighboursAndAddToQueueIfValid(mat, queue, visited, cell[0], cell[1]);

        }

        return mat;

    }

    

    private void UpdateNeighboursAndAddToQueueIfValid(

        int[][] mat, 

        Queue<int[]> queue, 

        bool[,] visited,

        int row,

        int col

    )

    {

        // up

        this.UpdateCellAndAddToQueueIfValid(mat, queue, visited, row, col, row - 1, col);

        // down

        this.UpdateCellAndAddToQueueIfValid(mat, queue, visited, row, col, row + 1, col);

        // left

        this.UpdateCellAndAddToQueueIfValid(mat, queue, visited, row, col, row, col - 1);

        // right

        this.UpdateCellAndAddToQueueIfValid(mat, queue, visited, row, col, row, col + 1);

    }

    

    private void UpdateCellAndAddToQueueIfValid(

        int[][] mat, 

        Queue<int[]> queue, 

        bool[,] visited,

        int parentRow,

        int parentCol,

        int row,

        int col

    )

    {

        if ( row < 0 

            || row >= mat.Length

            || col < 0

            || col >= mat[0].Length

            || visited[row, col]

           )

        {

            return;

        }        

        mat[row][col] = mat[parentRow][parentCol] + 1;

        visited[row, col] = true;

        queue.Enqueue(new int[] { row, col });

    }

    

    private void AddZeroCellsToQueue(int[][] mat, Queue<int[]> queue, bool[,] visited)

    {

        for (int i = 0; i < mat.Length; ++i)

        {

            for (int j = 0; j < mat[0].Length; ++j)

            {

                if (mat[i][j] == 0)

                {

                    queue.Enqueue(new int[] {i, j});

                    visited[i, j] = true;

                }

            }

        }

    }

Complexity: O(m * n)