Quick Overview

A grid shortest-path coding question: a map holds fire stations, residences and impassable lakes, and for every residence you return the length of the shortest four-directional route from the nearest station plus a charge looked up in a capped distance table. It tests graph search on grids, unreachable cells and exact output ordering.

Nearest Fire Station Distance and Capped Charge for Every Residence in a Grid with Lakes

Company: LinkedIn

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

A city map is a grid in which every cell holds `0` for a fire station, `-1` for a residence, or `-2` for a lake. A fire truck moves one cell at a time up, down, left or right. It may drive through fire stations and residences but never through a lake. For every residence, find its distance from the nearest fire station, then the amount the city pays for a truck to reach it. In the interview the distances came first and the charges were added as a second part. The report describes the charge as a base cost discounted for the closest residences, the base cost a little farther out, a surcharge that grows with each further step, and a cap, without giving the percentages; this version therefore passes the schedule in as a table of whole-number charges. ### Function Signature ```python def residence_charges(grid: list[list[int]], charges: list[int]) -> list[list[int]]: ``` ### Rules - The distance of a residence is the smallest number of moves on any route from any fire station to it, where each move goes to an edge-adjacent cell inside the grid and no route enters a lake. This equals the Manhattan distance when no lake is in the way. A reachable residence always has a distance of at least 1. - A residence at distance `d` costs `charges[d - 1]` when `d <= len(charges)`. For any larger distance the charge is `charges[-1]`, so the last entry acts as the cap. - A residence that no fire station can reach (for example one cut off by lakes, or any residence when the grid has no fire station) has distance `-1` and charge `-1`. - Return one `[row, col, distance, charge]` list for every residence, ordered by `row` ascending and then by `col` ascending. Rows and columns are 0-indexed. Return `[]` when the grid has no residence. ### Constraints - `rows >= 1`, `cols >= 1` and `rows * cols <= 10^5`; every row has the same length. - Every cell is `0`, `-1` or `-2`. The grid may contain any number of fire stations, including none. - `1 <= len(charges) <= 10^5` - `0 <= charges[i] <= 10^9` ### Examples **Example 1** ```text Input: grid = [[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], charges = [80, 100, 120, 130] Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]] ``` ```text S R R L L R R R R ``` (S = fire station, R = residence, L = lake.) The only station is at `(0, 0)`. The lakes in row 1 force every route into row 2 around the right side, so `(2, 0)` is 6 moves away even though its Manhattan distance is 2. Distances 5 and 6 are beyond the table, so they pay its last entry, 130. **Example 2** ```text Input: grid = [[-1, -1, 0], [0, -2, -1], [-1, -1, -1]], charges = [50, 70] Output: [[0, 0, 1, 50], [0, 1, 1, 50], [1, 2, 1, 50], [2, 0, 1, 50], [2, 1, 2, 70], [2, 2, 2, 70]] ``` There are stations at `(0, 2)` and `(1, 0)`, and each residence uses the nearer one. For example, `(2, 1)` is 2 moves from `(1, 0)` through `(2, 0)` but 3 moves from `(0, 2)`. **Example 3** ```text Input: grid = [[-1, -2, 0, -1]], charges = [5, 9] Output: [[0, 0, -1, -1], [0, 3, 1, 5]] ``` The lake at `(0, 1)` cuts `(0, 0)` off from the only station, while `(0, 3)` is one move away.

Overview: A grid shortest-path coding question: a map holds fire stations, residences and impassable lakes, and for every residence you return the length of the shortest four-directional route from the nearest station plus a charge looked up in a capped distance table. It tests graph search on grids, unreachable cells and exact output ordering.

Read the full LinkedIn Software Engineer interview experience this question came from

A city map is a rectangular grid in which every cell holds `0` for a fire station, `-1` for a residence, or `-2` for a lake. A fire truck moves one cell at a time up, down, left or right, staying inside the grid. It may drive through fire stations and residences but never through a lake. For every residence, find its distance from the nearest fire station, then the amount the city pays for a truck to reach it. The charge schedule is passed in as a table `charges` of whole-number charges. ## Rules - The distance of a residence is the smallest number of moves on any route from any fire station to it, where each move goes to an edge-adjacent cell inside the grid and no route enters a lake. This equals the Manhattan distance when no lake is in the way. A reachable residence always has a distance of at least 1. - A residence at distance `d` costs `charges[d - 1]` when `d <= len(charges)`. For any larger distance the charge is `charges[-1]` (the last entry), so the last entry acts as the cap. - A residence that no fire station can reach (for example one cut off by lakes, or any residence when the grid has no fire station) has distance `-1` and charge `-1`. - Return one `[row, col, distance, charge]` list for every residence, ordered by `row` ascending and then by `col` ascending. Rows and columns are 0-indexed. Fire stations and lakes get no entry. Return `[]` when the grid has no residence. ## Constraints - `rows >= 1`, `cols >= 1` and `rows * cols <= 10^5`; every row has the same length. - Every cell is `0`, `-1` or `-2`. The grid may contain any number of fire stations, including none. - `1 <= len(charges) <= 10^5` - `0 <= charges[i] <= 10^9` - Every distance is below `10^5` and every charge is at most `10^9`, so no value exceeds `2^31 - 1`: a 32-bit `int` is enough in Java and C++. ## Example 1 ```text Input: grid = [[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], charges = [80, 100, 120, 130] Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]] ``` The only station is at `(0, 0)`. The lakes in row 1 force every route around the right side and back along row 2, so `(2, 0)` is 6 moves away even though its Manhattan distance is 2. Distances 5 and 6 are beyond the table, so they pay its last entry, 130. ## Example 2 ```text Input: grid = [[-1, -2, 0, -1]], charges = [5, 9] Output: [[0, 0, -1, -1], [0, 3, 1, 5]] ``` The lake at `(0, 1)` cuts `(0, 0)` off from the only station, so it reports `-1, -1`, while `(0, 3)` is one move away and pays `charges[0] = 5`.

Constraints

  • rows >= 1, cols >= 1 and rows * cols <= 10^5; every row has the same length.
  • Every cell is 0 (fire station), -1 (residence) or -2 (lake). The grid may contain any number of fire stations, including none.
  • 1 <= len(charges) <= 10^5
  • 0 <= charges[i] <= 10^9
  • Every distance is below 10^5 and every charge is at most 10^9, so no value exceeds 2^31 - 1 (32-bit int in Java and C++).

Examples

Input: ([[0, -1, -1], [-2, -2, -1], [-1, -1, -1]], [80, 100, 120, 130])

Expected Output: [[0, 1, 1, 80], [0, 2, 2, 100], [1, 2, 3, 120], [2, 0, 6, 130], [2, 1, 5, 130], [2, 2, 4, 130]]

Explanation: Source example 1: lakes in row 1 force a detour, so (2, 0) is 6 moves away (Manhattan 2); distance 4 = len(charges) uses charges[3], distances 5 and 6 pay the cap 130.

Input: ([[-1, -1, 0], [0, -2, -1], [-1, -1, -1]], [50, 70])

Expected Output: [[0, 0, 1, 50], [0, 1, 1, 50], [1, 2, 1, 50], [2, 0, 1, 50], [2, 1, 2, 70], [2, 2, 2, 70]]

Explanation: Source example 2: two stations, each residence uses the nearer one; (2, 1) is 2 moves away (no diagonal moves), so it pays charges[1] = 70.

Hints

  1. A truck may pass through residences and other fire stations but never a lake, so when lakes sit in the way the true distance can be much larger than the Manhattan distance.
  2. Each residence only needs its distance to whichever fire station is nearest, not to any particular station.
  3. Once a distance d is known the charge is a direct table lookup: entry d - 1 while d <= len(charges), otherwise the last entry; a residence no station can reach reports -1 for both.

Loading coding console...

Show the approach

Approach

Algorithm: run one breadth-first search seeded with every fire station at distance 0 (a multi-source BFS). Pop cells in FIFO order; for each of the four edge-adjacent neighbours inside the grid that is not a lake and has not been discovered yet, record distance = current distance + 1 and push it. Residences and stations are both passable; lakes are never entered. Then scan the grid row by row, column by column, and for each residence emit [row, col, d, charge], where charge = charges[d - 1] if d <= len(charges), otherwise charges[-1]; an undiscovered residence emits [row, col, -1, -1].

Invariant: the queue always holds cells in nondecreasing distance order, and every cell at distance k from the nearest station is discovered before any cell at distance k + 1. Seeding all stations together is equivalent to adding a virtual source joined to every station by a zero-cost edge, so the first time a cell is discovered its recorded distance is the length of the shortest lake-avoiding route from the nearest station. A cell never discovered has no lake-free route to any station, so it is reported as -1, -1.

Correctness of the output: the final scan visits cells in row-major order, which is exactly the required (row ascending, col ascending) order, and only cells holding -1 produce entries, so stations and lakes are never emitted. Because every reachable residence has d >= 1, charges[d - 1] is always a valid index when d <= len(charges), and the last entry is used for every larger distance.

Edge cases: no station (every residence is -1, -1), no residence (return []), a 1x1 grid, a single row or column, a residence sealed in by lakes, a station sealed in by lakes (it serves no one), len(charges) == 1 (every reachable residence pays charges[0]), and maze-like lake layouts where the route distance far exceeds the Manhattan distance. Every distance is below 10^5 and every charge at most 10^9, so 32-bit integers suffice.

Time complexity:
O(rows * cols)
Space complexity:
O(rows * cols)