LeetCode 130 · Medium · Graphs

Surrounded Regions

A board holds "X" and "O". A region of Os connected up, down, left or right is captured, turned into X, when none of its cells touches the edge of the board. Change the board in place.

O(m·n)time
O(m·n)space (recursion)
3 passesmark the safe ones first

rows of X / O separated by ; · 1–6 rows × 1–7 columns · LeetCode's [["X","O"],...] works too

Call stack capture frames, bottom → top · the shaded path on the board

public void solve(char[][] board) { int rows = board.length; int cols = board[0].length; for (int r = 0; r < rows; r++) { // 1. edge regions: O -> T for (int c = 0; c < cols; c++) { boolean edge = r == 0 || r == rows - 1 || c == 0 || c == cols - 1; if (board[r][c] == 'O' && edge) { capture(board, r, c); } } } for (int r = 0; r < rows; r++) { // 2. surrounded: O -> X for (int c = 0; c < cols; c++) { if (board[r][c] == 'O') { board[r][c] = 'X'; } } } for (int r = 0; r < rows; r++) { // 3. T -> O for (int c = 0; c < cols; c++) { if (board[r][c] == 'T') { board[r][c] = 'O'; } } }}private void capture(char[][] board, int r, int c) { if (r < 0 || c < 0 || r == board.length || c == board[0].length || board[r][c] != 'O') { return; } board[r][c] = 'T'; capture(board, r + 1, c); capture(board, r - 1, c); capture(board, r, c + 1); capture(board, r, c - 1);}
pass
—
(r, c)
—
depth
0
T cells
0
captured
0

Why it works

  1. Brute force flood-fills every O region and checks whether it touches the edge. That is O(m·n) too, but it needs a second fill to flip each region, and the bookkeeping is easy to get wrong.
  2. Flip the question. Instead of finding the surrounded regions, find the safe ones: an O survives exactly when it is joined to an edge O. A DFS from every edge O marks all of them T. Whatever O is left after that is surrounded.
  3. O(m·n) time: each cell turns O → T at most once and each pass scans the board once. The recursion can go O(m·n) deep for a snake-shaped region, which on a big board can throw StackOverflowError in Java; an explicit ArrayDeque stack avoids that.
  4. Pitfall: the passes must run in order. Restoring T → O before flipping O → X would capture the safe cells too. And only edge cells start a capture; starting from an inner O marks a surrounded region as safe.
  5. Related: Pacific Atlantic Water Flow (417) and Number of Enclaves (1020) use the same start-from-the-border search.