994. Rotting Oranges

Description

You are given an m x n grid where each cell can have one of three values:

• 0 representing an empty cell,

• 1 representing a fresh orange, or

• 2 representing a rotten orange.

Every minute, any fresh orange that is 4-directionally adjacent to a rotten orange becomes rotten.

Return the minimum number of minutes that must elapse until no cell has a fresh orange. If this is impossible, return -1.

Constraints

• m == grid.length

• n == grid[i].length

• 1 <= m, n <= 10

• grid[i][j] is 0, 1, or 2.

Approach

Links

• Binarysearch

• GeeksforGeeks

• Leetcode

• ProgramCreek

• YouTube

Examples

Example 1

Input: grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]

Output: 4

Explanation:

Example 2

Input: grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]

Output: -1

Explanation: The orange in the bottom left corner (row 2, column 0) is never rotten, because rotting only happens 4-directionally.

Example 3

Input: grid = [[0, 2]]

Output: 0

Explanation: Since there are already no fresh oranges at minute 0, the answer is just 0.

Solutions

Solution 1

/**
 * Time complexity : 
 * Space complexity : 
 */

class Solution {
    private final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0) {
            return -1;
        }
        List<int[]> rottenCells = new ArrayList<>();
        int freshOranges = 0;
        
        for(int r = 0; r < grid.length; r++) {
            for(int c = 0; c < grid[0].length; c++) {
                if(grid[r][c] == 2) {
                    rottenCells.add(new int[]{r, c});
                }
                if(grid[r][c] == 1) {
                    freshOranges++;
                }
            }
        }
        
        int minutesElapsed = rottenCells.isEmpty()? 0: -1;
        
        while(!rottenCells.isEmpty()) {
            minutesElapsed++;
            List<int[]> newRottenCells = new ArrayList();
            for(int[] rottenCell: rottenCells) {
                for(int[] dir: dirs) {
                    int x = rottenCell[0] + dir[0];
                    int y = rottenCell[1] + dir[1];
                    if(x >= 0 && x < grid.length && y >= 0 && y < grid[0].length && grid[x][y] == 1) {
                        freshOranges--;
                        grid[x][y] = 2;
                        newRottenCells.add(new int[]{x, y});
                    }
                }
            }
            rottenCells = newRottenCells;
        }
        
        return freshOranges == 0? minutesElapsed: -1;
    }
}

Follow up