Compute nearest gate distance in grid

Q: Compute nearest gate distance in grid

This question evaluates grid traversal, distance propagation, obstacle handling, and in-place matrix update competencies within the Coding & Algorithms domain. It is commonly asked in technical interviews to assess algorithmic problem-solving and traversal strategies under obstacle and complexity constraints, representing a practical application-level problem rather than purely conceptual theory.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

You are given an m x n grid representing a floor plan.

0 = a gate
-1 = a blocked cell (wall/obstacle); cannot be entered
INF = an empty cell (a large integer such as 2^31 - 1 )

For every empty cell, fill it with the Manhattan distance (number of up/down/left/right steps) to its nearest gate. If an empty cell cannot reach any gate, leave it as INF.

Requirements

Update the grid in place .
Movement is only in 4 directions.

Example

Input:

INF  -1   0  INF
INF INF INF  -1
INF  -1 INF  -1
0    -1 INF INF

Output:

3  -1  0  1
2   2  1 -1
1  -1  2 -1
0  -1  3  4

Constraints (typical)

1 <= m, n <= 200
Grid values are only in { -1, 0, INF }

Compute nearest gate distance in grid

Quick Overview

Requirements

Example

Constraints (typical)

Comments (0)