Not a member of GistPad yet?
Sign Up,
it unlocks many cool features!
- 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;
- }
- }
RAW Paste Data
Copied
