ZOMATO Coding Question – Solved

```
To solve the problem of determining the minimum time required for all fresh oranges in a grid to become rotten, or deciding if it is impossible, the core idea revolves around simulating the spread of rot using a breadth-first search (BFS) approach. This type of problem fits naturally into graph traversal or multi-source BFS paradigms because the grid can be seen as a graph where each cell is a node connected to its adjacent nodes (up, down, left, right).

---

Step 1: Understand the Problem Setup

- The grid consists of cells that can be empty (0), contain fresh oranges (1), or contain rotten oranges (2).
- Rotten oranges infect adjacent fresh oranges simultaneously at each time step (minute).
- The goal is to find the minimum number of minutes until no fresh orange remains.
- If there are fresh oranges that can never be reached by rot (e.g., isolated by empty cells), return -1.

---

Step 2: Representing the Spread of Rot

- Each rotten orange acts as a source of infection.
- At minute 0, all rotten oranges begin to spread rot to their neighbors.
- The rot spreads simultaneously, meaning all rotten oranges infect their adjacent fresh oranges at the same time.
- This parallel spreading naturally suggests using BFS starting from all rotten oranges at once.

---

Step 3: Multi-source BFS Initialization

- Traverse the grid to:
- Identify all rotten oranges, and add their positions to a queue.
- Count the number of fresh oranges present.
- The queue now contains all initial "sources" of rot that will spread outwards.
- The count of fresh oranges keeps track of how many still need to be infected.

---

Step 4: Perform BFS to Simulate the Rotting Process

- Initialize a time counter at zero.
- While the queue is not empty and fresh oranges remain:
- For each rotten orange in the current queue (level in BFS), infect all adjacent fresh oranges.
- For each infected fresh orange:
- Change its state to rotten in the grid.
- Decrement the fresh orange count.
- Add the newly rotten orange’s position to the queue for the next iteration.
- Increment the time counter after processing one layer, representing one minute passing.
- Continue this process until either:
- All fresh oranges have become rotten, or
- The queue is empty but fresh oranges remain (meaning some fresh oranges are unreachable).

---

Step 5: Handling Boundary Conditions and Adjacency

- For each rotten orange processed:
- Check its four neighbors (up, down, left, right).
- Only infect neighbors that are within grid bounds and are fresh oranges.
- This ensures no out-of-bounds errors occur, and rot only spreads to valid fresh oranges.

---

Step 6: Determining the Result

- If after BFS completes, the fresh orange count is zero, return the total time taken.
- If fresh oranges remain, return -1 indicating some oranges could never rot.
- If there were no fresh oranges at the start, the answer is 0 since no infection spreading is needed.

---

Step 7: Complexity and Efficiency

- Each cell is visited at most once when it becomes rotten.
- BFS runs in O(N*M), where N and M are grid dimensions.
- This is efficient and practical for typical grid sizes.

---

Step 8: Example to Illustrate

- Suppose a grid with some rotten and fresh oranges:
- Add initial rotten oranges to the queue.
- In minute 1, rotten oranges infect their adjacent fresh neighbors.
- Those neighbors become rotten and will infect others in minute 2, and so on.
- The time counter reflects how many "layers" of infection have passed.

---

Step 9: Summary of Approach

- Use a queue to hold all rotten oranges at the current time step.
- Use BFS to spread rot to fresh oranges, updating the queue with newly rotten oranges.
- Track how many fresh oranges remain to know when all are rotten.
- Return the number of minutes passed or -1 if not all fresh oranges can be infected.

By thinking in terms of multi-source BFS and careful state tracking, you can simulate the simultaneous rotting process and find the minimum time efficiently.
```