286. Walls And Gates - Explanation

Description

You are given a $m \times n$ 2D grid initialized with these three possible values:

-1 - A water cell that can not be traversed.
0 - A treasure chest.
INF - A land cell that can be traversed. We use the integer 2^31 - 1 = 2147483647 to represent INF.

Fill each land cell with the distance to its nearest treasure chest. If a land cell cannot reach a treasure chest then the value should remain INF.

Assume the grid can only be traversed up, down, left, or right.

Modify the grid in-place.

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

Example 2:

Input: [
  [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}

Topics

Recommended Time & Space Complexity

You should aim for a solution with O(m * n) time and O(m * n) space, where m is the number of rows and n is the number of columns in the given grid.

Hint 1

A brute force solution would be to iterate on each land cell and run a BFS from that cells to find the nearest treasure chest. This would be an O((m * n)^2) solution. Can you think of a better way? Sometimes it is not optimal to go from source to destination.

Hint 2

We can see that instead of going from every cell to find the nearest treasure chest, we can do it in reverse. We can just do a BFS from all the treasure chests in grid and just explore all possible paths from those chests. Why? Because in this approach, the treasure chests self mark the cells level by level and the level number will be the distance from that cell to a treasure chest. We don't revisit a cell. This approach is called Multi-Source BFS. How would you implement it?

Hint 3

We insert all the cells (row, col) that represent the treasure chests into the queue. Then, we process the cells level by level, handling all the current cells in the queue at once. For each cell, we mark it as visited and store the current level value as the distance at that cell. We then try to add the neighboring cells (adjacent cells) to the queue, but only if they have not been visited and are land cells.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

2D Array (Grid) Traversal - Iterating through rows and columns of a matrix
Breadth First Search (BFS) - Finding shortest paths in unweighted graphs/grids
Multi-Source BFS - Starting BFS from multiple sources simultaneously for optimal distance calculation
Backtracking - Exploring all paths with state restoration for brute force solutions

1. Brute Force (Backtracking)

Intuition

For every empty cell (INF), we try to find the shortest path to any treasure (0) by exploring all 4 directions using backtracking DFS.

DFS explores all possible paths from the cell until it hits a treasure (distance 0), a wall (-1), or goes out of bounds.
We use a visited grid so the current path doesn't revisit cells (prevents infinite loops in cycles).
The answer for that cell is the minimum distance found among all DFS paths.

This works but is slow because we repeat DFS from many cells and re-explore the same areas again and again.

Algorithm

Let INF represent empty rooms that need a distance.
For each cell in the grid:
- If it is INF, run DFS(cell) to compute the minimum distance to a 0.
DFS(r, c):
- If out of bounds / wall (-1) / already visited → return INF.
- If current cell is a treasure (0) → return 0.
- Mark (r, c) as visited.
- Try all 4 directions and take:
  - min(1 + DFS(neighbor))
- Unmark (r, c) (backtrack).
- Return the minimum found.
Update grid[r][c] with the returned minimum distance.

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)

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);
                }
            }
        }
    }
}

class Solution {
public:
    vector<vector<int>> directions = {{1, 0}, {-1, 0},
                                      {0, 1}, {0, -1}};
    int INF = 2147483647;
    vector<vector<bool>> 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<bool>(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);
                }
            }
        }
    }
};

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);
                }
            }
        }
    }
}

class Solution {
    private val directions = arrayOf(
        intArrayOf(1, 0), intArrayOf(-1, 0),
        intArrayOf(0, 1), intArrayOf(0, -1)
    )
    private val INF = 2147483647
    private lateinit var visit: Array<BooleanArray>
    private var rows = 0
    private var cols = 0

    private fun dfs(grid: Array<IntArray>, r: Int, c: Int): Int {
        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
        var res = INF
        for (dir in directions) {
            val cur = dfs(grid, r + dir[0], c + dir[1])
            if (cur != INF) {
                res = minOf(res, 1 + cur)
            }
        }
        visit[r][c] = false
        return res
    }

    fun islandsAndTreasure(grid: Array<IntArray>): Unit {
        rows = grid.size
        cols = grid[0].size
        visit = Array(rows) { BooleanArray(cols) }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == INF) {
                    grid[r][c] = dfs(grid, r, c)
                }
            }
        }
    }
}

class Solution {
    func islandsAndTreasure(_ grid: inout [[Int]]) {
        let ROWS = grid.count
        let COLS = grid[0].count
        let INF = 2147483647
        let directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
        var visit = Array(repeating: Array(repeating: false, count: COLS), count: ROWS)

        func dfs(_ r: Int, _ c: Int) -> Int {
            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
            var 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 0..<ROWS {
            for c in 0..<COLS {
                if grid[r][c] == INF {
                    grid[r][c] = dfs(r, c)
                }
            }
        }
    }
}

Time & Space Complexity

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$ .

2. Breadth First Search

Intuition

BFS is perfect for shortest path in an unweighted grid.
From one empty cell (INF), we expand level-by-level (distance 0, 1, 2, ...). The first time we reach a treasure cell (0), we are guaranteed that distance is the minimum steps needed.

This approach runs a BFS separately for every INF cell, so it's simpler to think about, but can still be slow because many BFS runs repeat the same work.

Algorithm

Define 4 directions (up, down, left, right) and let INF represent empty rooms.
For each cell (r, c) in the grid:
- If grid[r][c] == INF, run BFS(r, c) to find the nearest treasure distance.
- Replace grid[r][c] with that returned distance.
BFS(sr, sc):
- Initialize a queue with (sr, sc) and a visited[ROWS][COLS].
- Set steps = 0.
- While the queue is not empty:
  - Process exactly the current queue size (one BFS "layer").
  - If any popped cell is a treasure (grid[row][col] == 0), return steps.
  - Otherwise, push valid neighbors (in bounds, not visited, not a wall (-1)) into the queue.
  - After finishing the layer, increment steps.
- If BFS ends without finding a treasure, return INF (no reachable treasure).

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)

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);
                }
            }
        }
    }
}

class Solution {
public:
    int ROWS, COLS;
    vector<vector<int>> directions = {{1, 0}, {-1, 0},
                                      {0, 1}, {0, -1}};
    int INF = INT_MAX;

    int bfs(vector<vector<int>>& grid, int r, int c) {
        queue<pair<int, int>> q;
        q.push({r, c});
        vector<vector<bool>> visit(ROWS, vector<bool>(COLS, false));
        visit[r][c] = true;
        int steps = 0;

        while (!q.empty()) {
            int size = q.size();
            for (int i = 0; i < size; i++) {
                auto [row, col] = q.front();
                q.pop();
                if (grid[row][col] == 0) return steps;
                for (auto& 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.push({nr, nc});
                    }
                }
            }
            steps++;
        }
        return INF;
    }

    void islandsAndTreasure(vector<vector<int>>& grid) {
        ROWS = grid.size();
        COLS = grid[0].size();

        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);
                }
            }
        }
    }
};

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);
                }
            }
        }
    }
}

class Solution {
    private val directions = arrayOf(
        intArrayOf(1, 0), intArrayOf(-1, 0),
        intArrayOf(0, 1), intArrayOf(0, -1)
    )
    private val INF = 2147483647

    fun islandsAndTreasure(grid: Array<IntArray>): Unit {
        val rows = grid.size
        val cols = grid[0].size

        fun bfs(r: Int, c: Int): Int {
            val q = ArrayDeque<Pair<Int, Int>>()
            q.add(Pair(r, c))
            val visit = Array(rows) { BooleanArray(cols) }
            visit[r][c] = true
            var steps = 0

            while (q.isNotEmpty()) {
                repeat(q.size) {
                    val (row, col) = q.removeFirst()
                    if (grid[row][col] == 0) {
                        return steps
                    }
                    for (dir in directions) {
                        val nr = row + dir[0]
                        val nc = col + dir[1]
                        if (nr in 0 until rows && nc in 0 until cols &&
                            !visit[nr][nc] && grid[nr][nc] != -1) {
                            visit[nr][nc] = true
                            q.add(Pair(nr, nc))
                        }
                    }
                }
                steps++
            }
            return INF
        }

        for (r in 0 until rows) {
            for (c in 0 until cols) {
                if (grid[r][c] == INF) {
                    grid[r][c] = bfs(r, c)
                }
            }
        }
    }
}

Time & Space Complexity

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$ .

3. Multi Source BFS

Intuition

Instead of running BFS from every empty room, run BFS once starting from all treasures (0 cells) at the same time.

Why this works:

BFS spreads out in "waves" of distance 0, 1, 2, ...
If we start the queue with all treasures, the first time the wave reaches an empty cell, it must be from the closest treasure (because BFS guarantees the first visit is the shortest distance in an unweighted grid).
So each cell gets filled with its minimum distance to any treasure.

This avoids repeated work and is the optimal approach.

Algorithm

Put all treasure cells (grid[r][c] == 0) into a queue.
Mark them visited. Walls (-1) are never added.
Set dist = 0.
While the queue is not empty:
- Process all nodes currently in the queue (this is one BFS level = distance dist).
- For each cell popped:
  - Set grid[r][c] = dist (distance to nearest treasure).
  - Try its 4 neighbors:
    - If in bounds, not a wall, and not visited -> mark visited and push to queue.
- After finishing the level, do dist += 1.
After BFS ends, every reachable empty room has been updated with its shortest distance; unreachable rooms remain INF.

class Solution:
    def islandsAndTreasure(self, grid: List[List[int]]) -> None:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()
        q = deque()

        def addCell(r, c):
            if (min(r, c) < 0 or r == ROWS or c == COLS or
                (r, c) in visit or grid[r][c] == -1
            ):
                return
            visit.add((r, c))
            q.append([r, c])

        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == 0:
                    q.append([r, c])
                    visit.add((r, c))

        dist = 0
        while q:
            for i in range(len(q)):
                r, c = q.popleft()
                grid[r][c] = dist
                addCell(r + 1, c)
                addCell(r - 1, c)
                addCell(r, c + 1)
                addCell(r, c - 1)
            dist += 1

public class Solution {
    public void islandsAndTreasure(int[][] grid) {
        Queue<int[]> q = new LinkedList<>();
        int m = grid.length;
        int n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    q.add(new int[] { i, j });
                }
            }
        }
        if (q.size() == 0) return;

        int[][] dirs = { { -1, 0 }, { 0, -1 },
                         { 1, 0 }, { 0, 1 } };
        while (!q.isEmpty()) {
            int[] node = q.poll();
            int row = node[0];
            int col = node[1];
            for (int[] dir : dirs) {
                int r = row + dir[0];
                int c = col + dir[1];
                if (r >= m || c >= n || r < 0 ||
                    c < 0 || grid[r][c] != Integer.MAX_VALUE) {
                    continue;
                }
                q.add(new int[] { r, c });

                grid[r][c] = grid[row][col] + 1;
            }
        }
    }
}

class Solution {
public:
    void islandsAndTreasure(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();

        queue<pair<int, int>> q;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) {
                    q.push({i, j});
                }
            }
        }

        vector<vector<int>> dirs = {{-1, 0}, {1, 0},
                                    {0, -1}, {0, 1}};
        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();

            for (int i = 0; i < 4; i++) {
                int r = row + dirs[i][0];
                int c = col + dirs[i][1];

                if (r < 0 || r >= m || c < 0 ||
                    c >= n || grid[r][c] != INT_MAX) {
                    continue;
                }

                grid[r][c] = grid[row][col] + 1;
                q.push({r, c});
            }
        }
    }
};

class Solution {
    /**
     * @param {number[][]} grid
     */
    islandsAndTreasure(grid) {
        let ROWS = grid.length;
        let COLS = grid[0].length;
        let visit = new Set();
        let q = new Queue();

        /**
         * @param {number} r
         * @param {number} c
         */
        function addCell(r, c) {
            if (
                Math.min(r, c) < 0 ||
                r === ROWS ||
                c === COLS ||
                visit.has(r + ',' + c) ||
                grid[r][c] === -1
            ) {
                return;
            }
            visit.add(r + ',' + c);
            q.push([r, c]);
        }

        for (let r = 0; r < ROWS; r++) {
            for (let c = 0; c < COLS; c++) {
                if (grid[r][c] === 0) {
                    q.push([r, c]);
                    visit.add(r + ',' + c);
                }
            }
        }

        let dist = 0;
        while (!q.isEmpty()) {
            for (let i = q.size(); i > 0; i--) {
                let [r, c] = q.pop();
                grid[r][c] = dist;
                addCell(r + 1, c);
                addCell(r - 1, c);
                addCell(r, c + 1);
                addCell(r, c - 1);
            }
            dist += 1;
        }
    }
}

public class Solution {
    public void islandsAndTreasure(int[][] grid) {
        Queue<int[]> q = new Queue<int[]>();
        int m = grid.Length;
        int n = grid[0].Length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 0) q.Enqueue(new int[] { i, j });
            }
        }

        if (q.Count == 0) return;

        int[][] dirs = {
            new int[] { -1, 0 }, new int[] { 0, -1 },
            new int[] { 1, 0 }, new int[] { 0, 1 }
        };
        while (q.Count > 0) {
            int[] cur = q.Dequeue();
            int row = cur[0];
            int col = cur[1];
            foreach (int[] dir in dirs) {
                int r = row + dir[0];
                int c = col + dir[1];
                if (r >= m || c >= n || r < 0 ||
                    c < 0 || grid[r][c] != int.MaxValue) {
                    continue;
                }
                q.Enqueue(new int[] { r, c });

                grid[r][c] = grid[row][col] + 1;
            }
        }
    }
}

class Solution {
    fun islandsAndTreasure(grid: Array<IntArray>): Unit {
        val m = grid.size
        val n = grid[0].size
        val q: Queue<Pair<Int, Int>> = LinkedList()

        for (i in 0 until m) {
            for (j in 0 until n) {
                if (grid[i][j] == 0) {
                    q.add(Pair(i, j))
                }
            }
        }
        if (q.isEmpty()) return

        val dirs = arrayOf(
            intArrayOf(-1, 0), intArrayOf(0, -1),
            intArrayOf(1, 0), intArrayOf(0, 1)
        )

        while (q.isNotEmpty()) {
            val (row, col) = q.poll()
            for (dir in dirs) {
                val r = row + dir[0]
                val c = col + dir[1]
                if (r !in 0 until m || c !in 0 until n ||
                    grid[r][c] != Int.MAX_VALUE) {
                    continue
                }
                q.add(Pair(r, c))
                grid[r][c] = grid[row][col] + 1
            }
        }
    }
}

struct Item: Hashable {
    let r: Int
    let c: Int
}

class Solution {
    func islandsAndTreasure(_ grid: inout [[Int]]) {
        let ROWS = grid.count
        let COLS = grid[0].count
        var visit = Set<Item>()
        var q = Deque<Item>()

        func addCell(_ r: Int, _ c: Int) {
            if r < 0 || c < 0 || r >= ROWS || c >= COLS { return }
            let item = Item(r: r, c: c)
            if visit.contains(item) || grid[r][c] == -1 { return }
            visit.insert(item)
            q.append(item)
        }

        for r in 0..<ROWS {
            for c in 0..<COLS {
                if grid[r][c] == 0 {
                    let item = Item(r: r, c: c)
                    q.append(item)
                    visit.insert(item)
                }
            }
        }

        var dist = 0
        while !q.isEmpty {
            let count = q.count
            for _ in 0..<count {
                let item = q.removeFirst()
                let r = item.r, c = item.c
                grid[r][c] = dist
                addCell(r + 1, c)
                addCell(r - 1, c)
                addCell(r, c + 1)
                addCell(r, c - 1)
            }
            dist += 1
        }
    }
}

impl Solution {
    pub fn islands_and_treasure(grid: &mut Vec<Vec<i32>>) {
        let m = grid.len();
        let n = grid[0].len();
        let mut q = VecDeque::new();

        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 0 {
                    q.push_back((i, j));
                }
            }
        }
        if q.is_empty() {
            return;
        }

        let dirs: [(i32, i32); 4] = [(-1, 0), (0, -1), (1, 0), (0, 1)];
        while let Some((row, col)) = q.pop_front() {
            for &(dr, dc) in &dirs {
                let r = row as i32 + dr;
                let c = col as i32 + dc;
                if r < 0 || r >= m as i32 || c < 0 || c >= n as i32 {
                    continue;
                }
                let (ur, uc) = (r as usize, c as usize);
                if grid[ur][uc] != i32::MAX {
                    continue;
                }
                grid[ur][uc] = grid[row][col] + 1;
                q.push_back((ur, uc));
            }
        }
    }
}

Time & Space Complexity

Time complexity: $O(m * n)$
Space complexity: $O(m * n)$

Where $m$ is the number of rows and $n$ is the number of columns in the $grid$ .

Common Pitfalls

Starting BFS from Empty Rooms Instead of Treasures

A common mistake is to run BFS from each empty room to find the nearest treasure, resulting in O((m*n)^2) time complexity. The optimal approach is multi-source BFS starting from all treasures simultaneously, which processes each cell exactly once.

Not Distinguishing Walls from Unvisited Cells

Walls are represented by -1 and should never be added to the queue or updated. Confusing the wall value with the infinity value (2147483647) for empty rooms can cause incorrect distance calculations or infinite loops.

Updating Distance Before Adding to Queue

In BFS, the distance should be updated when a cell is first discovered (added to the queue), not when it is processed (removed from the queue). Updating too late can result in cells being added to the queue multiple times with different distances, leading to incorrect results and inefficiency.