Orange Rotting Problem Statement

Consider a grid containing oranges. Each cell in this grid can hold one of three integer values:

Value 0: Represents an empty cell.

Value 1: Represents a fresh orange.

Value 2: Represents a rotten orange.

Every second, any fresh orange adjacent (in the four cardinal directions) to a rotten orange turns rotten.

The task is to determine the minimum time required for all fresh oranges to become rotten. Return -1 if it's impossible to rot all fresh oranges.

Input:

The first line contains two integers 'N' and 'M', denoting the grid's number of rows and columns. The next 'N' lines each contain 'M' space-separated integers, representing rows of the grid.

Output:

A single integer representing the minimum time after which no fresh orange remains. Return -1 if it is impossible.

Example:

Input: N = 3, M = 3 grid = [ [2,1,1], [1,1,0], [0,1,1] ] Output: 4

Explanation: At the end of 4 minutes, all oranges have rotted.

Constraints:

1

Question

Orange Rotting Problem Statement

Consider a grid containing oranges. Each cell in this grid can hold one of three integer values:

Value 0: Represents an empty cell.
Value 1: Represents a fresh orange.
Value 2: Represents a rotten orange.

Every second, any fresh orange adjacent (in the four cardinal directions) to a rotten orange turns rotten.

The task is to determine the minimum time required for all fresh oranges to become rotten. Return -1 if it's impossible to rot all fresh oranges.

Input:

The first line contains two integers 'N' and 'M', denoting the grid's number of rows and columns. The next 'N' lines each contain 'M' space-separated integers, representing rows of the grid.

Output:

A single integer representing the minimum time after which no fresh orange remains. Return -1 if it is impossible.

Example:

Input: N = 3, M = 3 grid = [ [2,1,1], [1,1,0], [0,1,1] ] Output: 4

Explanation: At the end of 4 minutes, all oranges have rotted.

Constraints:

1 <= N <= 500
1 <= M <= 500
0 <= grid[i][j] <= 2
Time Limit: 1 sec

Note:

Implement your solution without printing anything, as the printing is handled elsewhere.

Accepted Answer

The task is to determine the minimum time required for all fresh oranges to become rotten in a grid.

Create a queue to store the rotten oranges and their time of rotting.
Iterate through the grid to find the initial rotten oranges and add them to the queue.
Perform BFS by popping each rotten orange from the queue, rot adjacent fresh oranges, and add them to the queue with updated time.
Continue until the queue is empty, keeping track of the maximum time taken to rot all oranges.
If any fresh oranges remain after BFS, return -1; otherwise, return the maximum time taken.
Example: For the input grid [ [2,1,1], [1,1,0], [0,1,1] ], the minimum time required is 4.