How should I practice Rotten Oranges / Grid Infection BFS?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Lyft online assessment problems in FastPrep.

Is Rotten Oranges / Grid Infection BFS associated with Lyft?

FastPrep tags this as a Lyft coding interview or online assessment practice problem when the problem catalog has that company context.

Problem · Matrix

Rotten Oranges / Grid Infection BFS

Learn this problem

● MediumLyftOA

Problem statement

You are given a two-dimensional grid representing cells in an infection simulation. Each cell has one of three values:

0: empty
1: fresh
2: infected

Each minute, every currently infected cell simultaneously infects its 4-directional fresh neighbors. Fresh cells infected during the current minute can only infect other cells in later minutes.

Return the minimum number of minutes needed until there are no fresh cells left. If some fresh cell can never be infected, return -1. If there are no fresh cells at the start, return 0.

Function

minimumMinutesToInfectAll(grid: int[][]) → int

Examples

Example 1

grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]return = 4

The infection spreads level by level from the initial infected cell. The last fresh cell is infected after 4 minutes.

Example 2

grid = [[2, 1, 1], [0, 1, 1], [1, 0, 1]]return = -1

The fresh cell in the lower-left corner is isolated by empty cells, so it can never be infected.

Example 3

grid = [[0, 2]]return = 0

There are no fresh cells at the start.

Constraints

grid is a rectangular matrix.
Each cell is 0, 1, or 2.
Infection spreads only in the four orthogonal directions.