Practice/Spotify/Leetcode 286. Walls and Gates

Leetcode 286. Walls and Gates

CodingMust

Problem

You are given a 2D grid representing a building layout with three types of cells:

• Empty rooms: represented by the value 2147483647 (INT_MAX)
• Barriers: represented by -1 (impassable walls)
• Exit points: represented by 0 (doors leading outside)

Your task is to modify the grid in-place so that each empty room contains the distance to its nearest exit point. The distance is measured as the minimum number of steps needed to reach an exit, where each step moves to an adjacent cell (up, down, left, or right). Barriers and exits should remain unchanged.

If an empty room cannot reach any exit point (blocked by barriers), it should remain as 2147483647.

Requirements

1. Modify the input grid in-place
2. Calculate the shortest distance from each empty room to any exit point
3. Only horizontal and vertical movement is allowed (no diagonal movement)
4. Barriers block movement and should not be modified
5. Exit points should remain as 0
6. Empty rooms that cannot reach any exit should remain as 2147483647

Constraints

• 1 <= rooms.length, rooms[i].length <= 250
• rooms[i][j] is either -1, 0, or 2147483647
• There is at least one cell with value 0 (at least one exit exists)
• Time complexity should be O(m * n) where m and n are the grid dimensions
• Space complexity should be O(m * n) for the worst case

Examples

Example 1:

` Input: rooms = [[2147483647, -1, 0, 2147483647], [2147483647, 2147483647, 2147483647, -1], [2147483647, -1, 2147483647, -1], [0, -1, 2147483647, 2147483647]]

Output: [[3, -1, 0, 1], [2, 2, 1, -1], [1, -1, 2, -1], [0, -1, 3, 4]]

Explanation:

• The room at (0,0) is 3 steps from the exit at (3,0)
• The room at (0,3) is 1 step from the exit at (0,2)
• The room at (3,2) is 3 steps away from the nearest exit `

Example 2:

` Input: rooms = [[2147483647, 2147483647], [2147483647, 0]]

Output: [[2, 1], [1, 0]]

Explanation: All rooms measure their distance from the single exit at the bottom-right corner. `

Example 3:

` Input: rooms = [[0]]

Output: [[0]]

Explanation: Single cell that is already an exit point. `