How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

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.

Input: [[0,2]]

Expected Output: 0

Explanation: No fresh oranges exist at the start, so zero minutes are required.

Input: [[0]]

Expected Output: 0

Explanation: An empty cell with no fresh oranges needs 0 minutes.

Input: [[1]]

Expected Output: -1

Explanation: A lone fresh orange with no rotten neighbor can never rot.

Input: [[2,2],[2,2]]

Expected Output: 0

Explanation: All oranges already rotten — 0 minutes.

Input: [[1,2]]

Expected Output: 1

Explanation: The single fresh orange rots in 1 minute from its rotten neighbor.

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.

Input: [0,0], [5,5], 100, [], []

Expected Output: true

Explanation: No buses; direct walk costs |5|+|5| = 10 <= 100.

Input: [0,0], [5,5], 9, [], []

Expected Output: false

Explanation: Direct walk costs 10, which is greater than k = 9, and there is no bus to help.

Input: [0,0], [5,5], 10, [], []

Expected Output: true

Explanation: Direct walk costs exactly 10 = k, which is allowed.

Input: [0,0], [0,0], 0, [], []

Expected Output: true

Explanation: Start equals end; zero walking required.

Input: [0,0], [100,0], 0, [[0,0],[100,0]], [[0,1]]

Expected Output: true

Explanation: Station 0 sits on start and station 1 sits on end; board and alight with 0 walking, ride free.

Input: [0,0], [20,0], 2, [[1,0],[5,0],[15,0],[19,0]], [[0,1],[2,3]]

Expected Output: false

Explanation: The two bus components are disjoint; walking the 10-unit gap between (5,0) and (15,0) blows past k = 2.

Input: [0,0], [20,0], 2, [[1,0],[5,0],[15,0],[19,0]], [[0,1],[1,2],[2,3]]

Expected Output: true

Explanation: All four stations form one component; walk 1 to (1,0), ride free to (19,0), walk 1 to end: total 2 <= 2.

Input: [-3,-3], [3,3], 12, [], []

Expected Output: true

Explanation: Direct walk over negative coordinates costs |6|+|6| = 12 = k.

Input: [-3,-3], [3,3], 11, [], []

Expected Output: false

Explanation: Direct walk costs 12 > k = 11, with no bus available.

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.

Quick Overview

This question evaluates graph and grid traversal skills, state modeling over time, and constrained reachability combining free transit edges with Manhattan-distance walking.