Java: 01 Matrix

Thought Process

To solve this problem, we use a Breadth-First Search (BFS) approach. We start by initializing a queue with all cells containing 0, as these are the starting points. Hence, cells with 0 are pushed into the queue while cells with 1 are flagged as -1 to indicate they are unprocessed. During BFS, we explore each cell's four neighbors (up, down, left, right). If a neighbor is -1, we update its value to the cell's value + 1 and add it to the queue. This process continues until the queue is empty. 

class Solution {
    public int[][] updateMatrix(int[][] mat) {
        
        Queue<int[]> qu = new LinkedList<>();

        int row = mat.length;
        int col = mat[0].length;
        for(int i=0;i<row;i++){
            for(int j=0;j<col;j++){

                if(mat[i][j]==0)
                    qu.offer(new int[]{i,j});
                else
                    mat[i][j] = -1; // Flaged
            }
        }

        // Good way to iterate in all 4 direction
        int[] xDir = {1,-1,0,0};
        int[] yDir = {0,0,1,-1};

        while(!qu.isEmpty()){

            int[] arr = qu.poll();
            int x = arr[0];
            int y = arr[1];

            for(int i=0;i<4;i++){

                int x1 = x + xDir[i];
                int y1 = y + yDir[i];

                // If out of bound OR already visited
                if(x1>=row || x1<0 || y1>=col || y1<0 || mat[x1][y1]!=-1)
                    continue;

                mat[x1][y1] = mat[x][y]+1;
                qu.offer(new int[]{x1,y1});
            }
        }
        return mat;
    }
}

Code Complexity

Time Complexity: O(n * m)

The algorithm processes each cell in the matrix once, making the time complexity
O(n * m), where 'n' is the number of rows and 'm' is the number of columns.

Space Complexity: O(n * m)

The space complexity is determined by the queue used for BFS, which can store up to O(n * m) cells in the worst case.

Code copied!