bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
MediumGraphsLC 286

Walls And Gates

You are given an m x n grid rooms initialized with these three possible values. -1 A wall or an obstacle. 0 A gate. INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647. Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.

Asked at 11 companies
AmazonAppleBloomberg
Hints
  • 1.Think about what data structure fits Walls And Gates
  • 2.Consider the brute force complexity and how to optimize
  • 3.Can you trade space for time?
LeetCodeNeetCode