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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Surrounded Regions and Graphs problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →