Posts Rotten Oranges (geeksforgeeks - SDE Sheet)
Post
Cancel

Rotten Oranges (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given a grid of dimension nxm where each cell in the grid can have values 0, 1 or 2 which has the following meaning:

  • 0 : Empty cell
  • 1 : Cells have fresh oranges
  • 2 : Cells have rotten oranges

We have to determine what is the earliest time after which all the oranges are rotten. A rotten orange at index [i,j] can rot other fresh orange at indexes [i-1,j], [i+1,j], [i,j-1], [i,j+1] (up, down, left and right) in unit time.

geeksforgeeks

SOLUTION

Can be solved using multi-source BFS.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
class Solution {

    public int orangesRotting(int[][] grid) {

        int n = grid.length;
        int m = grid[0].length;

        // to keep track of time to rot each orange
        int[][] time = new int[n][m];

        // queue for multi source BFS
        Queue<int[]> q = new LinkedList<>();

        // Traverse the grid to find all initially rotten oranges
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 2) {
                    q.add(new int[]{i, j});
                }
            }
        }

        // BFS to rot adjacent fresh oranges
        while (!q.isEmpty()) {

            // Get the coordinates of the current rotten orange
            int i = q.peek()[0];
            int j = q.peek()[1];

            // Remove the rotten orange from the queue
            q.poll();

            // Arrays to represent the 4 possible directions (right, left, down, up)
            int[] x = {0, 0, 1, -1};
            int[] y = {1, -1, 0, 0};

            // Check all 4 possible directions
            for (int k = 0; k < 4; k++) {

                int nextX = i + x[k]; // Next row index
                int nextY = j + y[k]; // Next column index

                // check bounds
                if (nextX < 0 || nextY < 0 || nextX >= n || nextY >= m || grid[nextX][nextY] == 0 || grid[nextX][nextY] == 2) {
                    continue;
                }

                // If the next cell has a fresh orange, it gets rotted
                // It will eventually rot its neighboring oranges at later time
                // So, we need to add it to the queue
                q.add(new int[]{nextX, nextY});

                // Mark the orange as rotten in the grid
                // This is to avoid visiting this orange again
                grid[nextX][nextY] = 0;

                // Update the time to rot this orange
                // It will be 1 more than its already rotten neighbor
                time[nextX][nextY] = time[i][j] + 1;

            }
        }

        // Initialize the variable to track the maximum time taken to rot all oranges
        int maxTime = 0;

        // Traverse the grid to check if any fresh oranges are left and find the maximum time
        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                // If a fresh orange remains, return -1 (not all oranges can be rotted)
                if (grid[i][j] == 1) {
                    return -1;
                }

                // Update the maximum time taken to rot all oranges
                maxTime = Math.max(maxTime, time[i][j]);

            }
        }

        return maxTime;
    }
}
This post is licensed under CC BY 4.0 by the author.