Find Each Cell's Nearest Source
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given an `m x n` grid containing `1` for source cells and `0` for regular cells, compute for every cell the shortest 4-directional distance to any source cell. Moving up, down, left, or right costs 1 step. Return an `m x n` matrix of distances, where every source cell has distance `0`. If the grid contains no source cells, return `-1` for every cell.
Quick Answer: This question evaluates understanding of shortest-path computation and distance labeling in grid-based graphs, measuring competency in algorithmic problem solving and efficient traversal strategies.
Given an m x n grid where 1 represents a source cell and 0 represents a regular cell, compute the shortest distance from every cell to any source cell. You may move up, down, left, or right, and each move costs 1 step. Return an m x n matrix of distances. Every source cell has distance 0. If the grid contains no source cells, return -1 for every cell. If the grid is empty, return an empty list.
Constraints
- 0 <= m
- 0 <= n
- 0 <= m * n <= 100000
- grid[i][j] is either 0 or 1
- All rows in grid have the same length
Examples
Input: ([[0,0,0],[0,1,0],[0,0,0]],)
Expected Output: [[2,1,2],[1,0,1],[2,1,2]]
Explanation: The source is in the center. Each cell's distance is its Manhattan distance to the center source.
Input: ([[1,0,0],[0,0,0],[0,0,1]],)
Expected Output: [[0,1,2],[1,2,1],[2,1,0]]
Explanation: There are two sources. Each cell uses the shorter distance to either the top-left or bottom-right source.
Hints
- Instead of running a search from every regular cell, consider starting from all source cells at the same time.
- A breadth-first search processes cells in increasing distance order when every move has the same cost.