Katkat

Find Each Cell's Nearest Source

DoorDashSoftware Engineer · Onsite

Last updated

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 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.