Notification Spread Time
Devices sit in a grid. Each minute, every device already holding a push notification forwards it to its idle four-directional neighbours. Some cells are empty (no device). Report how many minutes until every device has the notification, or -1 if some device can never be reached.
Problem
Given a grid where 0 = empty cell, 1 = idle device, 2 = device already notified, each minute any idle device adjacent (up/down/left/right) to a notified device becomes notified. Return the minutes until no idle device remains, or -1 if impossible.
Input
A grid of size r×c (1 ≤ r, c ≤ 300) with values in {0, 1, 2}.
Output
A single integer — minutes elapsed, or -1 if some device stays idle.
Constraints
- 1 ≤ r, c ≤ 300
- Cells are 0, 1, or 2
- Spread is four-directional
Examples
Example 1
Input
grid = [[2,1,1],[1,1,0],[0,1,1]]
Output
4
The notification radiates from the top-left; the bottom-right device is reached after 4 minutes.
Example 2
Input
grid = [[2,1,1],[0,1,1],[1,0,1]]
Output
-1
The device at the bottom-left is cut off by empty cells and never gets notified.