## 286. Walls and Gates

You are given a m x n 2D grid initialized with these three possible values.

1. -1 - A wall or an obstacle.
2. 0 - A gate.
3. 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.

For example, given the 2D grid:

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

After running your function, the 2D grid should be:

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

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Brute Force) [Time Limit Exceeded]

\n

The brute force approach is simple, we just implement a breadth-first search from each empty room to its nearest gate.

\n

While we are doing the search, we use a 2D array called distance to keep track of the distance from the starting point. It also implicitly tell us whether a position had been visited so it won\'t be inserted into the queue again.

\n
private static final int EMPTY = Integer.MAX_VALUE;\nprivate static final int GATE = 0;\nprivate static final int WALL = -1;\nprivate static final List<int[]> DIRECTIONS = Arrays.asList(\n        new int[] { 1,  0},\n        new int[] {-1,  0},\n        new int[] { 0,  1},\n        new int[] { 0, -1}\n);\n\npublic void wallsAndGates(int[][] rooms) {\n    if (rooms.length == 0) return;\n    for (int row = 0; row < rooms.length; row++) {\n        for (int col = 0; col < rooms[0].length; col++) {\n            if (rooms[row][col] == EMPTY) {\n                rooms[row][col] = distanceToNearestGate(rooms, row, col);\n            }\n        }\n    }\n}\n\nprivate int distanceToNearestGate(int[][] rooms, int startRow, int startCol) {\n    int m = rooms.length;\n    int n = rooms[0].length;\n    int[][] distance = new int[m][n];\n    Queue<int[]> q = new LinkedList<>();\n    q.add(new int[] { startRow, startCol });\n    while (!q.isEmpty()) {\n        int[] point = q.poll();\n        int row = point[0];\n        int col = point[1];\n        for (int[] direction : DIRECTIONS) {\n            int r = row + direction[0];\n            int c = col + direction[1];\n            if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] == WALL\n                    || distance[r][c] != 0) {\n                continue;\n            }\n            distance[r][c] = distance[row][col] + 1;\n            if (rooms[r][c] == GATE) {\n                return distance[r][c];\n            }\n            q.add(new int[] { r, c });\n        }\n    }\n    return Integer.MAX_VALUE;\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nFor each point in the size grid, the gate could be at most steps away.

\n
• \n
• \n

Space complexity : .\nThe space complexity depends on the queue\'s size. Since we won\'t insert points that have been visited before into the queue, we insert at most points into the queue.

\n
• \n
\n
\n

#### Approach #2 (Breadth-first Search) [Accepted]

\n

Instead of searching from an empty room to the gates, how about searching the other way round? In other words, we initiate breadth-first search (BFS) from all gates at the same time. Since BFS guarantees that we search all rooms of distance d before searching rooms of distance d + 1, the distance to an empty room must be the shortest.

\n
private static final int EMPTY = Integer.MAX_VALUE;\nprivate static final int GATE = 0;\nprivate static final List<int[]> DIRECTIONS = Arrays.asList(\n        new int[] { 1,  0},\n        new int[] {-1,  0},\n        new int[] { 0,  1},\n        new int[] { 0, -1}\n);\n\npublic void wallsAndGates(int[][] rooms) {\n    int m = rooms.length;\n    if (m == 0) return;\n    int n = rooms[0].length;\n    Queue<int[]> q = new LinkedList<>();\n    for (int row = 0; row < m; row++) {\n        for (int col = 0; col < n; col++) {\n            if (rooms[row][col] == GATE) {\n                q.add(new int[] { row, col });\n            }\n        }\n    }\n    while (!q.isEmpty()) {\n        int[] point = q.poll();\n        int row = point[0];\n        int col = point[1];\n        for (int[] direction : DIRECTIONS) {\n            int r = row + direction[0];\n            int c = col + direction[1];\n            if (r < 0 || c < 0 || r >= m || c >= n || rooms[r][c] != EMPTY) {\n                continue;\n            }\n            rooms[r][c] = rooms[row][col] + 1;\n            q.add(new int[] { r, c });\n        }\n    }\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : .

\n

If you are having difficulty to derive the time complexity, start simple.

\n

Let us start with the case with only one gate. The breadth-first search takes at most steps to reach all rooms, therefore the time complexity is . But what if you are doing breadth-first search from gates?

\n

Once we set a room\'s distance, we are basically marking it as visited, which means each room is visited at most once. Therefore, the time complexity does not depend on the number of gates and is .

\n
• \n
• \n

Space complexity : .\nThe space complexity depends on the queue\'s size. We insert at most points into the queue.

\n
• \n
\n
'