Find Each Cell's Nearest Source
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
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.
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.
Input: ([[0,0],[0,0]],)
Expected Output: [[-1,-1],[-1,-1]]
Explanation: There are no source cells, so every output cell is -1.
Input: ([[1]],)
Expected Output: [[0]]
Explanation: The only cell is a source, so its distance is 0.
Input: ([],)
Expected Output: []
Explanation: The grid is empty, so the result is also an empty list.
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.