Skip to main content

130. Surrounded Regions

medium

Flip every 'O' region in a grid to 'X' unless it touches the border. Invert the problem — do BFS/DFS from the border 'O's to mark survivors, then flip everything else.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'. A region is captured by flipping all 'O's into 'X's in that surrounded region.

Constraints

  • m == board.length
  • n == board[i].length
  • 1 <= m, n <= 200
  • board[i][j] is 'X' or 'O'.

Examples

Example 1

Input
board = [['X','X','X','X'],['X','O','O','X'],['X','X','O','X'],['X','O','X','X']]
Output
[['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','O','X','X']]

Explanation: The bottom-left 'O' touches the border so it survives. The inner region is captured.

Example 2

Input
board = [['X']]
Output
[['X']]

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Going inward and asking 'am I trapped?' is messy. Invert it — go outward from the border.

Hint 2

Every 'O' on the border (or connected to one) is safe. Mark those first.

Hint 3

BFS/DFS from each border 'O', flagging connected 'O's as safe (e.g. flip them to '#'). After that sweep, every remaining 'O' is captured — flip to 'X'. Then flip the '#'s back to 'O'.

Solution approach

Reveal approach

BFS-from-borders. First pass: iterate the perimeter (row 0, row m-1, col 0, col n-1). For each 'O' found, launch DFS or BFS that flips every connected 'O' to a sentinel '#'. This marks all 'O's that survive (touch border directly or indirectly). Second pass: scan the entire board — every remaining 'O' is surrounded so flip it to 'X', and every '#' is safe so flip it back to 'O'. The inversion trick is the whole point: 'is this region surrounded?' is hard to ask cell-by-cell, but 'is this region NOT surrounded' becomes a simple reachability check from the border. O(m*n) time, O(m*n) space worst case for the recursion stack.

Complexity

Time
O(m*n)
Space
O(m*n)

Related patterns

  • graph-dfs
  • graph-bfs
  • matrix
  • flood-fill

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google
  • Meta
  • Microsoft

More Graphs practice problems

See all Graphs problems →