Rotting Oranges | Dataford Interview Questions

Rotting Oranges (LeetCode 994).

Asked in the Round 1 stage. Reported follow-up: optimize the solution without using a separate visited array.

Contract

Implement def oranges_rotting(grid):. The input is a non-empty rectangular list of lists containing 0 for an empty cell, 1 for a fresh orange, or 2 for a rotten orange. Each minute, every rotten orange infects adjacent fresh oranges in the four cardinal directions. Return the minimum number of minutes required for all fresh oranges to rot, or -1 if some fresh orange can never be reached. The input grid may be modified in place.

Constraints

1 <= rows, cols <= 500
1 <= rows * cols <= 250000
Each cell contains only 0, 1, or 2
The grid is rectangular

Function Signature

def oranges_rotting(grid):

Your question is Rotting Oranges. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem