Subhra Jyoti Baroieditorial
Chat with me
← Daily Logs
LeetCode 130

Surrounded Regions

MediumJul 7, 2026graphbfsmulti-source

A fourth multi-source BFS from the border inward, but the flip is two-step instead of one: mark every border-connected 'O' as a throwaway 'T' first, then a final sweep turns the untouched 'O's into 'X' and folds the 'T's back to 'O' — the intermediate label is what keeps 'safe' and 'captured' distinguishable until that last pass.

The problem

Implement `solve(board)`, mutating an `m x n` board of `'X'` and `'O'` in place. Any region of `'O'`s that is fully surrounded by `'X'`s — meaning none of its cells touch the border, directly or through a chain of adjacent `'O'`s — gets flipped to `'X'`. Regions that reach the border, or connect to one that does, stay `'O'`.

'Surrounded' is a connectivity property, not a per-cell one: a single interior-looking `'O'` survives if it's chained to a border `'O'` through any path of `'O'`s, so the safe set has to be found by traversal, not by checking each cell's immediate neighbours.

The approach

Same multi-source seed as every earlier grid BFS in this log — scan the four border edges, push every `'O'` found there into the queue, mark each visited — except here 'visited' is encoded directly on the board: draining the queue overwrites each reached cell from `'O'` to `'T'`, a marker that means 'safe, don't touch' rather than a value that appears anywhere in the problem's own alphabet.

That third symbol is the whole trick. Once BFS finishes, the board holds exactly three states — `'X'` (never was an O), `'T'` (an O connected to the border), and `'O'` (an O that never got reached) — and a single final sweep can tell all three apart and act accordingly: leftover `'O'` had no path to the border, so it becomes `'X'`; `'T'` gets folded back to `'O'` since it was always safe.

Without the intermediate marker, the sweep would have nothing to distinguish 'safe O' from 'captured O' — flipping reached cells straight to `'X'` (or leaving them as `'O'`) collapses the two categories the moment BFS overwrites a cell, since both look identical by the time the sweep runs.

The solution

js
class Solution {
    /**
     * @param {character[][]} board
     * @return {void} Do not return anything, modify board in-place instead.
     */
    solve(board) {
        const visited = new Set()
        const q = []
        const boardRows = board.length
        const boardCols = board[0].length
        const directions = [[0,1], [0,-1], [1,0], [-1,0]]

        // Scanning all the border areas and pushing 'O' into the q for bfs
        for (let r = 0; r < boardRows; r++) {
            for (let c = 0; c < boardCols; c++) {
                const isBorder = r === 0 || r === boardRows - 1 || c === 0 || c === boardCols - 1
                if (isBorder && board[r][c] === 'O') {
                  q.push([r, c])
                  visited.add(`${r},${c}`)
                }
            }
        }

        // BFS from every border 'O', marking each one reachable as 'T'
        while (q.length) {
            const [r, c] = q.shift()
            board[r][c] = 'T'

            for (const [dr, dc] of directions) {
                const nr = r + dr
                const nc = c + dc
                const key = `${nr},${nc}`

                const nColInbound = nc >= 0 && nc < boardCols
                const nRowInbound = nr >= 0 && nr < boardRows
                const inBound = nColInbound && nRowInbound

                if (
                    inBound &&
                    board[nr][nc] === 'O' &&
                    !visited.has(key)
                ) {
                    visited.add(key)
                    q.push([nr, nc])
                }
            }
        }

        // Final sweep: 'O' (never reached border) -> 'X', 'T' (was border-connected) -> 'O'
        for (let r = 0; r < boardRows; r++) {
            for (let c = 0; c < boardCols; c++) {
                if (board[r][c] === 'O') board[r][c] = 'X'
                else if (board[r][c] === 'T') board[r][c] = 'O'
            }
        }
    }
}

Time O(R * C)Space O(R * C)

All entries