Walls And Gates Problem
Walls and Gates Problem – Medium Level Problem
You are given a 2D grid with m × n cells, where each cell can have one of these three values:
- -1 – Water (cannot be crossed).
- 0 – A treasure chest.
- INF – Land that can be crossed (represented by 2147483647).
What next?
Your task is to update each land cell (INF) with the distance to its nearest treasure chest (0). If a land cell cannot reach any treasure chest, its value should remain INF.
You can only move up, down, left, or right in the grid.
You can only move up, down, left, or right in the grid.
Example 1:
Input: [
[2147483647,-1,0,2147483647],
[2147483647,2147483647,2147483647,-1],
[2147483647,-1,2147483647,-1],
[0,-1,2147483647,2147483647]
]
Output: [
[3,-1,0,1],
[2,2,1,-1],
[1,-1,2,-1],
[0,-1,3,4]
]
[2147483647,-1,0,2147483647],
[2147483647,2147483647,2147483647,-1],
[2147483647,-1,2147483647,-1],
[0,-1,2147483647,2147483647]
]
Output: [
[3,-1,0,1],
[2,2,1,-1],
[1,-1,2,-1],
[0,-1,3,4]
]
Example 2:
Input: [
[0,-1],
[2147483647,2147483647]
]
Output: [
[0,-1],
[1,2]
]
[0,-1],
[2147483647,2147483647]
]
Output: [
[0,-1],
[1,2]
]
Constraints :
- m == grid.length
- n == grid[i].length
- 1 <= m, n <= 100
- grid[i][j] is one of {-1, 0, 2147483647}
Walls and Gates Problem - Solution
Recommendation for Time and Space Complexity – Aim for O(m × n) time and space, where m is rows and n is columns.
Hints for solving problems
Hint 1
A brute force approach checks each land cell and runs BFS to find the nearest treasure, which takes O((m × n)²). Instead, think about solving it in reverse.
Hint 2
Instead of starting from each land cell, start BFS from all treasure chests at once. This Multi-Source BFS updates distances level by level, ensuring no cell is revisited.
Hint 3
Add all treasure chest positions to a queue and process them level by level. For each cell, mark it visited, update its distance, and add its unvisited land neighbors to the queue.
There are mainly 3 approach to solve this problem-
- Brute Force(Backtracking) Method
- Breadth First Search Method
1. Brute Force(Backtracking) Method
In this approach, recursively explore all possible paths from each gate to every empty room. Update the shortest distance for each room along the way. Though simple, it is inefficient for large grids due to the high time complexity caused by repeated visits to the same rooms.
- Time complexity: O(m * n * 4^(m*n))
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns in the grid.
Code
C++
Java
Python
JavaScript
C++
class Solution {
public:
vector<vector<int>> directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
int INF = 2147483647;
vector<vector> visit;
int ROWS, COLS;
int dfs(vector<vector<int>>& grid, int r, int c) {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || grid[r][c] == -1 || visit[r][c]) {
return INF;
}
if (grid[r][c] == 0) {
return 0;
}
visit[r][c] = true;
int res = INF;
for (auto& dir : directions) {
int cur = dfs(grid, r + dir[0], c + dir[1]);
if (cur != INF) {
res = min(res, 1 + cur);
}
}
visit[r][c] = false;
return res;
}
void islandsAndTreasure(vector<vector<int>>& grid) {
ROWS = grid.size();
COLS = grid[0].size();
visit.assign(ROWS, vector(COLS, false));
for (int r = 0; r < ROWS; ++r) {
for (int c = 0; c < COLS; ++c) {
if (grid[r][c] == INF) {
grid[r][c] = dfs(grid, r, c);
}
}
}
}
};
Java
public class Solution {
private int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
private int INF = 2147483647;
private boolean[][] visit;
private int ROWS, COLS;
private int dfs(int[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || grid[r][c] == -1 || visit[r][c]) {
return INF;
}
if (grid[r][c] == 0) {
return 0;
}
visit[r][c] = true;
int res = INF;
for (int[] dir : directions) {
int cur = dfs(grid, r + dir[0], c + dir[1]);
if (cur != INF) {
res = Math.min(res, 1 + cur);
}
}
visit[r][c] = false;
return res;
}
public void islandsAndTreasure(int[][] grid) {
ROWS = grid.length;
COLS = grid[0].length;
visit = new boolean[ROWS][COLS];
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == INF) {
grid[r][c] = dfs(grid, r, c);
}
}
}
}
}
Python
class Solution:
def islandsAndTreasure(self, grid: List[List[int]]) -> None:
ROWS, COLS = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 2147483647
visit = [[False for _ in range(COLS)] for _ in range(ROWS)]
def dfs(r, c):
if (r < 0 or c < 0 or r >= ROWS or
c >= COLS or grid[r][c] == -1 or
visit[r][c]):
return INF
if grid[r][c] == 0:
return 0
visit[r][c] = True
res = INF
for dx, dy in directions:
res = min(res, 1 + dfs(r + dx, c + dy))
visit[r][c] = False
return res
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == INF:
grid[r][c] = dfs(r, c)
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {void}
*/
islandsAndTreasure(grid) {
let ROWS = grid.length;
let COLS = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const INF = 2147483647;
let visit = Array.from({ length: ROWS }, () =>
Array(COLS).fill(false));
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || grid[r][c] === -1 || visit[r][c]) {
return INF;
}
if (grid[r][c] === 0) {
return 0;
}
visit[r][c] = true;
let res = INF;
for (let [dx, dy] of directions) {
res = Math.min(res, 1 + dfs(r + dx, c + dy));
}
visit[r][c] = false;
return res;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (grid[r][c] === INF) {
grid[r][c] = dfs(r, c);
}
}
}
}
}
2. Breadth First Search Method
Start BFS from each gate (value 0) one at a time. Update distances for reachable empty rooms and stop exploring when you encounter walls or visited cells. While better than brute force, this still processes each gate separately, leading to redundant work.
- Time complexity: O((m * n)^2)
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns in the grid.
Code
C++
Java
Python
JavaScript
C++
public class Solution {
private int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
private int INF = 2147483647;
private int ROWS, COLS;
private int bfs(int[][] grid, int r, int c) {
Queue<int[]> q = new LinkedList<>();
q.add(new int[]{r, c});
boolean[][] visit = new boolean[ROWS][COLS];
visit[r][c] = true;
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) { int[] curr = q.poll(); int row = curr[0], col = curr[1]; if (grid[row][col] == 0) return steps; for (int[] dir : directions) { int nr = row + dir[0], nc = col + dir[1]; if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS &&
!visit[nr][nc] && grid[nr][nc] != -1) {
visit[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
steps++;
}
return INF;
}
public void islandsAndTreasure(int[][] grid) {
ROWS = grid.length;
COLS = grid[0].length;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == INF) {
grid[r][c] = bfs(grid, r, c);
}
}
}
}
}Java
public class Solution {
private int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
private int INF = 2147483647;
private int ROWS, COLS;
private int bfs(int[][] grid, int r, int c) {
Queue q = new LinkedList<>();
q.add(new int[]{r, c});
boolean[][] visit = new boolean[ROWS][COLS];
visit[r][c] = true;
int steps = 0;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
int[] curr = q.poll();
int row = curr[0], col = curr[1];
if (grid[row][col] == 0) return steps;
for (int[] dir : directions) {
int nr = row + dir[0], nc = col + dir[1];
if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS &&
!visit[nr][nc] && grid[nr][nc] != -1) {
visit[nr][nc] = true;
q.add(new int[]{nr, nc});
}
}
}
steps++;
}
return INF;
}
public void islandsAndTreasure(int[][] grid) {
ROWS = grid.length;
COLS = grid[0].length;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == INF) {
grid[r][c] = bfs(grid, r, c);
}
}
}
}
}
Python
class Solution:
def islandsAndTreasure(self, grid: List[List[int]]) -> None:
ROWS, COLS = len(grid), len(grid[0])
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
INF = 2147483647
def bfs(r, c):
q = deque([(r, c)])
visit = [[False] * COLS for _ in range(ROWS)]
visit[r][c] = True
steps = 0
while q:
for _ in range(len(q)):
row, col = q.popleft()
if grid[row][col] == 0:
return steps
for dr, dc in directions:
nr, nc = row + dr, col + dc
if (0 <= nr < ROWS and 0 <= nc < COLS and
not visit[nr][nc] and grid[nr][nc] != -1
):
visit[nr][nc] = True
q.append((nr, nc))
steps += 1
return INF
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == INF:
grid[r][c] = bfs(r, c)
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {void}
*/
islandsAndTreasure(grid) {
let ROWS = grid.length;
let COLS = grid[0].length;
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const INF = 2147483647;
let visit = Array.from({ length: ROWS }, () =>
Array(COLS).fill(false));
const bfs = (r, c) => {
const q = new Queue([[r, c]]);
const visit = Array.from({ length: ROWS }, () =>
Array(COLS).fill(false));
visit[r][c] = true;
let steps = 0;
while (!q.isEmpty()) {
let size = q.size();
for (let i = 0; i < size; i++) { const [row, col] = q.pop(); if (grid[row][col] === 0) return steps; for (let [dr, dc] of directions) { const nr = row + dr, nc = col + dc; if (nr >= 0 && nr < ROWS && nc >= 0 && nc < COLS &&
!visit[nr][nc] && grid[nr][nc] !== -1) {
visit[nr][nc] = true;
q.push([nr, nc]);
}
}
}
steps++;
}
return INF;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (grid[r][c] === INF) {
grid[r][c] = bfs(r, c);
}
}
}
}
}
