Solve Rotting Oranges and Bus Walk Reachability
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
LeetCode 994. Rotting Oranges.
2) Given start and end grid coordinates, an integer k (maximum walking distance), and a bidirectional graph of bus stations represented by coordinate pairs where bus travel is free and walking between any two points costs Manhattan distance, determine whether you can reach the end from the start using any sequence of bus rides plus walking with total walking distance ≤ k.
https://leetcode.com/problems/rotting-oranges/description/
Quick Answer: This question evaluates graph and grid traversal skills, state modeling over time, and constrained reachability combining free transit edges with Manhattan-distance walking.
Rotting Oranges
You are given an `m x n` grid where each cell can have one of three values:
- `0` representing an empty cell,
- `1` representing a fresh orange, or
- `2` representing a rotten orange.
Every minute, any fresh orange that is **4-directionally adjacent** (up, down, left, right) to a rotten orange becomes rotten.
Return the **minimum number of minutes** that must elapse until no cell has a fresh orange. If this is impossible, return `-1`.
**Example 1:**
Input: `grid = [[2,1,1],[1,1,0],[0,1,1]]`
Output: `4`
**Example 2:**
Input: `grid = [[2,1,1],[0,1,1],[1,0,1]]`
Output: `-1` (the orange in the bottom-left corner is never reached because it is blocked by empty cells).
**Example 3:**
Input: `grid = [[0,2]]`
Output: `0` (there are no fresh oranges at minute 0, so the answer is 0).
Constraints
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 10
- grid[i][j] is 0, 1, or 2
Examples
Input: [[2,1,1],[1,1,0],[0,1,1]]
Expected Output: 4
Explanation: Classic spread: the two corners take 4 minutes total to fully rot.
Input: [[2,1,1],[0,1,1],[1,0,1]]
Expected Output: -1
Explanation: The fresh orange at the bottom-left is isolated by empty cells and can never rot.
Hints
- Think multi-source BFS: all initially-rotten oranges start at minute 0 and spread together level by level.
- Count the fresh oranges up front. Each level of the BFS corresponds to one minute; decrement the fresh count as you rot each orange.
- After the BFS, if any fresh oranges remain (count > 0), it is impossible — return -1. If there were no fresh oranges to begin with, the answer is 0.
Bus Walk Reachability
You are given a `start` coordinate, an `end` coordinate, an integer `k` (the maximum total walking distance you are allowed), and a network of bus stations.
The stations are given as a list `stations`, where `stations[i] = [x, y]` is the coordinate of station `i`. The bus network is a **bidirectional graph** given as `bus_edges`, where each edge `[u, v]` connects station `u` and station `v` (0-indexed into `stations`). Riding the bus along these edges (and therefore moving freely between any stations in the same connected component) is **free**.
**Walking** between any two points costs the **Manhattan distance** `|x1 - x2| + |y1 - y2|` between them.
You may use any sequence of bus rides and walks. Return `true` if you can get from `start` to `end` with **total walking distance ≤ k**, and `false` otherwise.
**Example:**
Input: `start = [0,0]`, `end = [10,0]`, `k = 2`, `stations = [[1,0],[9,0]]`, `bus_edges = [[0,1]]`
Output: `true`
Explanation: Walk from `(0,0)` to station 0 at `(1,0)` (distance 1), ride the bus for free to station 1 at `(9,0)`, then walk from `(9,0)` to `(10,0)` (distance 1). Total walking = 2 ≤ k.
Constraints
- Coordinates are integers (may be negative).
- 0 <= k
- 0 <= number of stations
- bus_edges[i] = [u, v] with 0 <= u, v < number of stations; the graph is bidirectional.
- Walking distance uses the Manhattan metric.
Examples
Input: [0,0], [10,0], 2, [[1,0],[9,0]], [[0,1]]
Expected Output: true
Explanation: Walk 1 to station 0, free bus to station 1, walk 1 to end: total walking 2 <= 2.
Input: [0,0], [10,0], 1, [[1,0],[9,0]], [[0,1]]
Expected Output: false
Explanation: Minimum walking is 2 (1 to board, 1 to alight), which exceeds k = 1.
Hints
- Model start, end, and every bus station as nodes. Walking between any two nodes is an edge whose weight is their Manhattan distance.
- Each bus edge connects two stations with weight 0, since riding the bus is free. This means all stations in one connected component become mutually reachable at zero walking cost.
- Run Dijkstra from start using accumulated walking distance as the cost. The answer is whether the shortest walking distance to end is at most k.