This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

You are given a *m x n* 2D grid 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`2`

to represent^{31}- 1 = 2147483647`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## Solution

\n

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

\n\n

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

\n\n

'
\n\n

\n\n

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

\nWhile 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.

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

**Complexity analysis**

- \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

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.

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

**Complexity analysis**

- \n
- \n
Time complexity : .

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

\nLet 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?

\nOnce 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