PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

This question evaluates a candidate's understanding of graph traversal concepts, grid-based state propagation, and reachability analysis in time-evolving systems.

  • Medium
  • Amazon
  • Coding & Algorithms
  • Software Engineer

Compute fruit spoilage time in a grid

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an m×n grid representing kitchen cells: 0 for empty, 1 for fresh fruit, and 2 for spoiled fruit. Each minute, any fresh fruit adjacent (up, down, left, right) to a spoiled fruit becomes spoiled. Return the minimum number of minutes needed to spoil all fresh fruits, or -1 if it is impossible. Describe your algorithm, prove correctness at a high level, and analyze time and space complexity. Implement a function that computes the answer.

Quick Answer: This question evaluates a candidate's understanding of graph traversal concepts, grid-based state propagation, and reachability analysis in time-evolving systems.

You are given an `m x n` grid representing kitchen cells. Each cell holds one of three values: - `0` — an empty cell, - `1` — a cell with a fresh fruit, - `2` — a cell with a spoiled fruit. Each minute, any fresh fruit that is **4-directionally adjacent** (up, down, left, right) to a spoiled fruit becomes spoiled. Return the **minimum number of minutes** that must elapse until no cell has a fresh fruit. If this is impossible (some fresh fruit can never be reached), return `-1`. **Approach (multi-source BFS):** Treat every initially-spoiled cell as a BFS source and push them all into a queue. Count the number of fresh fruits. Process the queue layer by layer; each completed layer corresponds to one elapsed minute. When a spoiled cell spoils a fresh neighbor, decrement the fresh count and enqueue the newly-spoiled cell. Stop when the queue is empty. If any fresh fruit remains, return `-1`; otherwise return the number of layers processed. **Correctness (high level):** BFS from all initial sources simultaneously expands the spoiled region one ring at a time, so a fruit is reached at exactly the minute equal to its shortest grid-distance to the nearest initial source. The number of completed expansion layers therefore equals the time at which the last reachable fruit spoils. Any fresh fruit never dequeued is in no connected component containing a source, so it can never spoil, giving `-1`. **Complexity:** Time `O(m·n)` — each cell is enqueued and processed at most once. Space `O(m·n)` for the queue in the worst case.

Constraints

  • 1 <= m, n <= 10^3
  • grid[i][j] is 0, 1, or 2
  • The grid is processed in place; treat the input as mutable.

Examples

Input: ([[2,1,1],[1,1,0],[0,1,1]],)

Expected Output: 4

Explanation: Spoilage spreads outward from the top-left source. The farthest fresh fruit (bottom-right) spoils at minute 4.

Input: ([[2,1,1],[0,1,1],[1,0,1]],)

Expected Output: -1

Explanation: The fresh fruit at the bottom-left corner has no path of fresh/spoiled cells back to a source, so it can never spoil; return -1.

Input: ([[0,2]],)

Expected Output: 0

Explanation: There are no fresh fruits to spoil, so the answer is 0 minutes.

Input: ([[0]],)

Expected Output: 0

Explanation: An empty grid with no fruit at all takes 0 minutes.

Input: ([[1]],)

Expected Output: -1

Explanation: A lone fresh fruit with no spoiled source anywhere can never spoil; return -1.

Input: ([[2,2,2],[2,2,2]],)

Expected Output: 0

Explanation: Every cell is already spoiled, so 0 minutes elapse.

Input: ([[2,1,1,1,1,1,1,1,2]],)

Expected Output: 4

Explanation: Two sources at both ends spread inward; the middle fruits spoil last after 4 minutes (the two sources meet in the center).

Hints

  1. Run a single breadth-first search seeded with ALL initially-spoiled cells at once, rather than one BFS per source. The number of BFS layers you process equals the answer in minutes.
  2. Track the count of fresh fruits as you go. Decrement it every time you spoil a neighbor; if the count is still positive after the queue drains, some fruit was unreachable, so return -1.
  3. Watch the boundary cases: a grid with no fresh fruit at all takes 0 minutes, and increment the minute counter only for layers that actually spoil something.
Last updated: Jun 25, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Implement Top-p (Nucleus) Sampling in NumPy - Amazon (medium)
  • Implement Multi-Head Attention from Scratch in NumPy - Amazon (medium)
  • Detect and Break a Cycle in a Singly Linked List - Amazon (medium)
  • Caesar Cipher with Translation-Table Optimization - Amazon (medium)
  • Minimum Drone Delivery Time on a Ring of Hubs - Amazon (medium)