Rotting Oranges
Medium About 20 min Free, no account needed
How many minutes until the rot spreads everywhere?
The brief
In a grid, 0 is empty, 1 a fresh orange, 2 a rotten one. Every minute,
fresh oranges 4-adjacent to a rotten one rot. Return the minutes until no
fresh orange remains, or -1 if some never rot.
The obvious approach simulates minute by minute, rescanning the whole grid each time, O(cells * minutes). The hidden test is a 200x200 serpentine corridor that takes ~20,000 minutes to traverse, so the rescan is too slow. You need an approach that touches each cell only a constant number of times, O(cells).
Starter code
using System;
public class Solution
{
// TODO: return the number of minutes until no fresh orange remains; -1 if unreachable.
public int OrangesRotting(int[][] grid)
{
throw new NotImplementedException();
}
}How it is graded
Visible examples help you iterate. Hidden tests then cover edge cases and larger inputs, and every test reports server-measured time and allocated bytes.
Related guides
What it practices
- Breadth-first search
- Explore a graph or grid level by level for shortest unweighted distances and spreading processes.
Related katas
- Minimum Forward Jumps Medium Free Cross a jump array with the fewest hops, including dead ends, without enumerating every reachable edge.
- Number of Islands Medium Free Count the connected patches of land in a grid.
- Shortest Path in Binary Matrix Medium Free Shortest 8-directional path across an open grid - DFS wanders, BFS knows.
- Boats to Save People Medium Free Pair people into two-person boats under a weight limit, using as few boats as possible.