Solve BFS grid delivery routing
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
You are given an m×n grid representing a city: 'S' are DashMart stores, 'H' are homes, '.' are roads, and '#' are obstacles. Movement is allowed in four directions on roads only. For each home cell, compute the length of the shortest path to any store; if unreachable, return -1 for that home. Output an array of distances aligned to the list of homes. Provide the algorithm, complexity, and code. Follow-up: if new obstacles are added frequently between queries, explain how you would update distances efficiently without recomputing everything from scratch.
Quick Answer: This question evaluates proficiency in grid-based graph traversal and shortest-path computation, along with complexity analysis and handling dynamic changes, assessing skills in algorithm design, graph algorithms, and data structures within the Coding & Algorithms domain.
You are given an m×n grid representing a city. Each cell is one of:
- `'S'` — a DashMart store
- `'H'` — a home
- `'.'` — a road
- `'#'` — an obstacle (impassable)
From any cell you may move up, down, left, or right into a neighboring cell, as long as that neighbor is not an obstacle (`'#'`). Stores, homes, and roads are all traversable.
For every home cell `'H'`, compute the length of the shortest path (number of steps) to the **nearest** DashMart store `'S'`. If a home cannot reach any store, its distance is `-1`.
Return an array of distances, one per home, ordered by the homes' positions in row-major order (top-to-bottom, then left-to-right within each row).
**Approach:** Run a single multi-source BFS seeded from every store cell at distance 0 simultaneously. Because BFS explores cells in non-decreasing distance order, the first time BFS reaches any cell, it has found that cell's shortest distance to the closest store. After the BFS fills in distances for the whole reachable region, scan the grid in row-major order and collect the distance of each home.
**Follow-up (discuss, not coded):** If obstacles are added frequently between queries, recomputing the full BFS each time is wasteful. Options: (1) Adding an obstacle can only *increase* distances, so re-run BFS only from the affected frontier — invalidate the subtree of cells whose shortest path passed through the newly blocked cell and re-relax their neighbors (incremental/dynamic BFS, e.g. the D*-Lite family). (2) Precompute and cache the distance field; on an obstacle insertion, mark the blocked cell and lazily recompute only dirty regions. (3) For bursty edits, batch the obstacle additions and recompute once per batch instead of per edit.
Constraints
- 1 <= m, n (the grid may be empty; an empty grid returns []).
- Each cell is one of 'S', 'H', '.', '#'.
- There may be zero or more stores and zero or more homes.
- Movement is 4-directional (up/down/left/right); diagonal moves are not allowed.
- '#' cells are impassable; 'S', 'H', and '.' cells are all traversable.
- Distances are returned in row-major order of the home cells.
Examples
Input: ([['S', '.', 'H'], ['#', '.', '#'], ['H', '.', '.']],)
Expected Output: [2, 4]
Explanation: Home at (0,2) reaches store (0,0) via (0,0)->(0,1)->(0,2) = 2 steps. Home at (2,0) must go (2,0)->(2,1)->(1,1)->(0,1)->(0,0) = 4 steps (the obstacles at (1,0) and (1,2) block the shorter routes).
Input: ([['S', 'H']],)
Expected Output: [1]
Explanation: The home is directly adjacent to the store, so distance 1.
Hints
- Instead of running a separate BFS from each home, run ONE multi-source BFS seeded from all store cells at distance 0 at once. The first time BFS reaches a cell, that is its shortest distance to the closest store.
- Use a distance matrix initialized to -1 to double as the 'visited' marker: a cell with dist == -1 has not been reached yet, so unreachable homes naturally keep -1.
- After BFS fills the reachable region, scan the grid in row-major order (row by row, left to right) and append dist[i][j] for every 'H' cell to build the answer in the required order.