Walls and Gates

Walls and Gates is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph BFS - Connected Components / Island Counting subpattern.

Problem statement

Implement Solution.wallsAndGates(rooms). The parameter rooms is a rectangular grid, where each cell represents one room or barrier. Cells with value -1 are walls and cannot be entered, cells with value 0 are gates, and cells with value 2147483647 are empty rooms whose distances have not yet been filled.

Movement is allowed only between horizontally or vertically adjacent cells, and walls cannot be crossed. Modify rooms in place so that every empty room contains the minimum number of moves needed to reach any gate. An empty room with no possible route to a gate must remain 2147483647.

The method returns nothing; the required answer is the final contents of rooms after the in-place modification.

Example 1:

Input: rooms = [[2147483647,-1,0],[2147483647,2147483647,2147483647],[-1,2147483647,-1]] Output: [[4,-1,0],[3,2,1],[-1,3,-1]] Explanation: The gate at the top right reaches the open cells through the lower corridor. The wall cells are unchanged.

Example 2:

Input: rooms = [[2147483647,-1],[2147483647,2147483647]] Output: [[2147483647,-1],[2147483647,2147483647]] Explanation: There is no gate, so none of the empty rooms can receive a finite distance.

Example 3:

Input: rooms = [[0,2147483647,2147483647],[2147483647,-1,2147483647],[2147483647,2147483647,0]] Output: [[0,1,2],[1,-1,1],[2,1,0]] Explanation: Distances are measured from the nearer of the two gates, while the center wall remains -1.

Constraints:

- 1 <= rooms.length <= 250 - 1 <= rooms[0].length <= 250 - Every row in rooms has the same length as rooms[0].length - Each rooms[i][j] is one of -1, 0, or 2147483647 - The grid uses four-directional adjacency: up, down, left, and right

Topics and companies

Topics: Breadth-First Search, Matrix, Queue, Shortest Path.

How to practise Walls and Gates on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n), where m is the number of rows and n is the number of columns. time and O(m * n) for the BFS queue in the worst case. space.

Open Walls and Gates in the code editor, or read the Walls and Gates editorial for a worked solution with its approach and complexity analysis.

Where Walls and Gates sits in the DSA pattern sheet

Problems related to Walls and Gates

Other problems that use the same Graph BFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

Preparing this workspace.