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 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
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
\nTime complexity : .\nFor each point in the size grid, the gate could be at most steps away.
\nSpace 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.
\nInstead 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.
\nprivate 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
\nTime 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 .
\nSpace complexity : .\nThe space complexity depends on the queue\'s size. We insert at most points into the queue.
\n