Fill rooms with nearest gate distances

Q: Fill rooms with nearest gate distances

This question evaluates grid-based graph traversal and algorithmic problem-solving skills, including concepts such as multi-source breadth-first search, handling sentinel values, and performing in-place updates.

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

You are given an m×n integer grid representing rooms, where -1 is a wall, 0 is a gate, and INF (a large sentinel such as 2^31−

is an empty room. For each empty room, fill it with the minimum number of steps to the nearest gate using four-directional movement; if unreachable, leave it as INF. Implement an in-place algorithm, justify your traversal strategy (e.g., multi-source BFS), and analyze time and space complexity. Cover edge cases such as multiple gates, enclosed areas, and very large grids.

Fill rooms with nearest gate distances

Overview

Comments (0)