May 11, 2022

994. Rotting Oranges

994. Rotting Oranges

BFS. Time=O(n), space=O(n), where n is the size of the grid.

class Solution {
    public int orangesRotting(int[][] grid) {
        Queue<int[]> queue = new LinkedList<>();
        int freshOranges = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) {
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    freshOranges ++;
                }
            }
        }
        int minutes = 0;
        int[][] directions = {`{-1, 0}, {1, 0}, {0, -1}, {0, 1}`};
        while (!queue.isEmpty()) {
            if (freshOranges == 0) { // important!
                break;
            }
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] orange = queue.poll();
                for (int[] direction : directions) {
                    int row = orange[0] + direction[0];
                    int col = orange[1] + direction[1];
                    if (row >= 0 && col >= 0 && row < grid.length && col < grid[0].length) {
                        if (grid[row][col] == 1) {
                            grid[row][col] = 2;
                            freshOranges --;
                            queue.offer(new int[]{row, col});
                        }
                    }
                }   
            }
            minutes ++;
        }
        return freshOranges == 0 ? minutes : -1;
    }
}
comments powered by Disqus