130. Surrounded Regions

At a Glance

Topic: graphs
Pattern: DFS / Backtracking
Difficulty: Medium
Companies: Amazon, Meta, Microsoft, Google, Apple
Frequency: High
LeetCode: 130

Problem (one-liner)

Given board O/X, flip every O that cannot escape to the border to X. Border-connected O regions survive.

Recognition Cues

Surrounded ↔ not connected to boundary
Mark escape cells from border first (DFS/BFS)

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Loading diagram…

Approaches

Try each component — duplicate work — acceptable but cluttered.
Optimal — flood border O as safe; flip remaining O — O(nm).

Optimal Solution

Go

func solve(board [][]byte) {
	if len(board) == 0 {
		return
	}
	rows := len(board)
	cols := len(board[0])

	var flood func(row int, col int)
	flood = func(row int, col int) {
		if row < 0 || col < 0 || row >= rows || col >= cols {
			return
		}
		if board[row][col] != 'O' {
			return
		}
		board[row][col] = '#'
		flood(row+1, col)
		flood(row-1, col)
		flood(row, col+1)
		flood(row, col-1)
	}

	for col := 0; col < cols; col++ {
		flood(0, col)
		flood(rows-1, col)
	}
	for row := 0; row < rows; row++ {
		flood(row, 0)
		flood(row, cols-1)
	}

	for row := 0; row < rows; row++ {
		for col := 0; col < cols; col++ {
			if board[row][col] == 'O' {
				board[row][col] = 'X'
			} else if board[row][col] == '#' {
				board[row][col] = 'O'
			}
		}
	}
}

JavaScript

function solve(board) {
  if (board.length === 0) {
    return;
  }
  const rows = board.length;
  const cols = board[0].length;

  function flood(row, col) {
    if (row < 0 || col < 0 || row >= rows || col >= cols) {
      return;
    }
    if (board[row][col] !== 'O') {
      return;
    }
    board[row][col] = '#';
    flood(row + 1, col);
    flood(row - 1, col);
    flood(row, col + 1);
    flood(row, col - 1);
  }

  for (let col = 0; col < cols; col += 1) {
    flood(0, col);
    flood(rows - 1, col);
  }
  for (let row = 0; row < rows; row += 1) {
    flood(row, 0);
    flood(row, cols - 1);
  }

  for (let row = 0; row < rows; row += 1) {
    for (let col = 0; col < cols; col += 1) {
      if (board[row][col] === 'O') {
        board[row][col] = 'X';
      } else if (board[row][col] === '#') {
        board[row][col] = 'O';
      }
    }
  }
}