Quick Overview

Practice multi-source BFS to compute the nearest charging station for every vehicle in a grid. Work through empty inputs, missing stations, distance ties, and the distinction between nearest distances and exclusive assignments.

Find the Nearest Charging Station for Every Vehicle

Company: Spotify

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Onsite

Given a rectangular grid whose cells are `C` (charging station), `V` (vehicle), or `.` (empty), return the shortest distance from every vehicle to a charging station. Movement is one cell up, down, left, or right. The base problem has no obstacles; vehicles and stations do not block movement. ### Input and Output For this practice interface, return records `[row, column, distance]` for vehicle cells in row-major order, using zero-based coordinates. Use distance `-1` when there is no station. An empty grid or a grid with no vehicles returns an empty list. These output conventions normalize an interview prompt that did not specify a function signature; numerical grid-size bounds were not reported. For example, `[["V",".","C"],[".","V","."]]` returns `[[0,0,2],[1,1,2]]`. ### Clarifying Questions Why can the base-case distance also be described as Manhattan distance? What would change if some cells were walls? Can you avoid a separate visited set while retaining the original vehicle locations? ### What a Strong Answer Covers Explain the repeated-search baseline, then give a multi-source breadth-first search, its first-discovery invariant, and time and space in terms of grid rows and columns. Cover empty input, absent stations, adjacent vehicles and stations, and several equally near stations. ### Follow-up Questions How would you add obstacles? Why is finding each vehicle's nearest station different from assigning distinct stations to all vehicles?

Overview: Practice multi-source BFS to compute the nearest charging station for every vehicle in a grid. Work through empty inputs, missing stations, distance ties, and the distinction between nearest distances and exclusive assignments.

Given a rectangular grid of C (charging station), V (vehicle), and . (empty), return [row, column, distance] for every vehicle in row-major order, with zero-based coordinates. Distance is the minimum number of up, down, left, or right moves to any charging station. All cells are traversable: vehicles and stations do not block movement. Return -1 for a vehicle when no station exists. Return an empty list for an empty grid or a grid without vehicles. For example, [["V",".","C"],[".","V","."]] returns [[0,0,2],[1,1,2]].

Constraints

  • The grid is rectangular, with cells only C, V, or ..
  • Movement uses four neighboring cells, and every cell is traversable.
  • The grid may be empty; no numerical size bound was reported.

Examples

Input: ([['V', '.', 'C'], ['.', 'V', '.']],)

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

Explanation: Both vehicles are two moves from the sole station.

Input: ([['V', 'C']],)

Expected Output: [[0, 0, 1]]

Explanation: An adjacent station is one move away.

Hints

  1. Consider starting a search at all charging stations together.
  2. Keep the original grid available when emitting vehicle records.

Loading coding console...

Show the approach

Approach

Start breadth-first search simultaneously at every station, assigning distance zero to each. Each newly discovered cell has distance one more than the cell that reached it. BFS visits cells in nondecreasing path length, so the first discovery yields the minimum distance to any station. Scan the original grid in row-major order to emit only vehicle records. With no station the queue stays empty and all vehicle distances remain -1.

Time complexity:
O(R * C)
Space complexity:
O(R * C)