LeetCode 286: Walls and Gates
Problem Description
Explanation:
-
Algorithmic Idea:
- We can solve this problem using Breadth First Search (BFS).
- We start by iterating over all gates and enqueue their positions into the queue.
- Then, we perform BFS to traverse all cells starting from the gates and updating their distance to the nearest gate.
- During BFS, we update the distance of each cell by considering its neighboring cells and the current cell's distance.
-
Step-by-Step Iterations:
- Enqueue all gate positions into the queue.
- Perform BFS to update distances for all cells.
-
Time Complexity: O(m*n) where m and n are the dimensions of the grid.
-
Space Complexity: O(m*n) for the queue and visited array.
: :
Solutions
class Solution {
public void wallsAndGates(int[][] rooms) {
if (rooms == null || rooms.length == 0) return;
int m = rooms.length;
int n = rooms[0].length;
Queue<int[]> queue = new LinkedList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (rooms[i][j] == 0) {
queue.offer(new int[]{i, j});
}
}
}
int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int row = curr[0];
int col = curr[1];
for (int[] dir : dirs) {
int newRow = row + dir[0];
int newCol = col + dir[1];
if (newRow < 0 || newRow >= m || newCol < 0 || newCol >= n || rooms[newRow][newCol] != Integer.MAX_VALUE) {
continue;
}
rooms[newRow][newCol] = rooms[row][col] + 1;
queue.offer(new int[]{newRow, newCol});
}
}
}
}Related LeetCode Problems
Loading editor...