class Pair
{
    int first;
    int second;
    int step;
    Pair(int first, int second, int step)
    {
        this.first = first;
        this.second = second;
        this.step = step;
    }
}

class Solution {
    public ArrayList<ArrayList<Integer>> nearest(int[][] grid) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        
        int n = grid.length;
        int m = grid[0].length;
        
        Queue<Pair> q = new LinkedList<>();
        
        // visited array to mark which all 0's are visited
        boolean[][] visited = new boolean[n][m];
        // distance matrix that will store the nearest distance of 1's
        int[][] distance = new int[n][m];
        
        // step-1 adding all those indices into queue where we have as 1 and mark them visited
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                if(grid[i][j] == 1)
                {
                    q.add(new Pair(i,j,0));
                    visited[i][j] = true;
                    distance[i][j] = 0;
                }
            }
        }
        
        int[] deltaRow = {-1,1,0,0};
        int[] deltaCol = {0,0,1,-1};
        
        // step-2 traverse the stored indices in queue and check for neighbour 0's
        while(!q.isEmpty())
        {
            Pair pair = q.poll();
            int row = pair.first;
            int col = pair.second;
            int step = pair.step;
            
            // checking in all 4-directions
            for(int i=0; i<4; i++)
            {
                int nRow = row + deltaRow[i];
                int nCol = col + deltaCol[i];
                
                if(nRow >=0 && nRow < n && nCol >=0 && nCol < m)
                {
                    if(grid[nRow][nCol] == 0 && !visited[nRow][nCol])
                    {
                        q.add(new Pair(nRow, nCol, step+1));
                        visited[nRow][nCol] = true;
                        distance[nRow][nCol] = step+1;
                    }
                }
            }
        }
        
        // Step-3 convert the distance matrix into resulant array list
        for(int i=0; i<n; i++)
        {
            ArrayList<Integer> rowList = new ArrayList<>();
            for(int j=0; j<m; j++) 
            {
                rowList.add(distance[i][j]);
            }
            res.add(rowList);
        }
        return res;
    }
}