Rotting Apples Editorial

Practice Problem Link: Rotting Apples

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

You are given an n * m grid where each position can contain one of the three values:

Every day, all fresh apples which are adjacent to any rotten apple become rotten.

Two cells are adjacent if they have a common edge, i.e., each cell can have upto four adjacent cells.

Find the minimum number of days required for all the apples to be rotten. If this is not possible return -1.

Approach

The way to approach this problem is to use “Multisource BFS on a Grid”.  We can observe that fresh apples, adjacent to the rotten apples are rotten on day 1, then those adjacent to these apples are rotten on day 2, and so on. This is similar to a level order traversal on a graph, where the rotten apples are the initial root nodes. We can push all the initial rotten apple nodes into our queue and perform BFS on a grid, and calculate the total time taken. If all the fresh nodes cannot be rotten after the end of the BFS call, we return -1.

Analysis

• Time Complexity: O(n * m)
• Space Complexity: O(n * m)

Implementation

C++

int dx[] = {1, 0, -1, 0};
int dy[] = {0, 1, 0, -1};
bool isSafe(vector<vector<int> > &grid, int x, int y){
    int r = grid.size();
    int c = grid[0].size();
    return (x >= 0 && x < r && y >= 0 && y < c && grid[x][y] == 1);
}
int getDaysToRot(vector<vector<int>> &grid) {
    int r = grid.size();
    int c = grid[0].size();
    queue<pair<int, int>> q;
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(grid[i][j] == 2) {
				q.push({i, j});
			}
        }
    }
    int days = -1;
    while(!q.empty()) {
        int qs = q.size();
            while(qs--) {
            pair<int, int> p = q.front();
            int x = p.first;
            int y = p.second;
            q.pop();
            for(int i = 0; i < 4; i++){
                if(isSafe(grid, x + dx[i], y + dy[i])){
                    q.push({x + dx[i], y + dy[i]});
                    grid[x + dx[i]][y + dy[i]] = 2;
                }
            }
        }
        days += 1;
    }
    for(int i = 0; i < r; i++){
        for(int j = 0; j < c; j++){
            if(grid[i][j] == 1){
				return -1;
			}
        }
    }
    return days;
}

Java

class Solution {
	int getDaysToRot(int[][] grid) {
	    int[][] dir = {{0,-1}, {-1,0}, {0,1}, {1,0}};
		int r = grid.length;
		int c = grid[0].length;
		int time = 0, countOfOnes = 0;
		Queue<int[]> q = new LinkedList<>();
		for(int i = 0; i < r; i++){
			for(int j = 0; j < c; j++) { 
				if(grid[i][j] == 2) {
					q.add(new int[] {i,j});
				}
				if(grid[i][j] == 1) { 
					countOfOnes++;
				}
			}
		}
		if(countOfOnes == 0) { 
			return 0;
		}
		while(!q.isEmpty()) {
			int size = q.size();
			while(size-- > 0) {
				int[] temp = q.remove();
				int i = temp[0], j = temp[1];
				for(int l = 0; l < 4; l++){
					int nr = i + dir[l][0], nc = j + dir[l][1];
					if(nr < 0 || nc < 0 || nr == r || nc == c) {  
						continue;
					}
					if(grid[nr][nc] == 1) {
						countOfOnes -= 1;
						q.add(new int[] {nr,nc});
						grid[nr][nc] = 2;
					}
				}
			}
			if(q.size() > 0) {
				time += 1;
			}
		}
		if(countOfOnes == 0) {
			return time;
		}
		else {
			return -1;
		}
	}
}