Surrounded Regions
The key idea
An 'O' survives only if it is connected to the border. So flip the problem: find every border-connected 'O' and protect it, then capture all the rest. Search inward FROM the edges instead of testing each region for the absence of an escape.
Problem
You are given an m x n matrix board containing the characters 'X' and 'O'. Capture every region that is surrounded by 'X'.
A region is captured by flipping all 'O' cells into 'X' cells in that surrounded region. A cell is part of a surrounded region only if it is enclosed — an 'O' that is connected, 4-directionally, to any 'O' on the border of the board is not captured. Modify the board in place: every enclosed 'O' becomes 'X', and every border-connected 'O' stays 'O'.
Constraints
m == board.lengthn == board[i].length1 <= m, n <= 200board[i][j]is'X'or'O'
Examples
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"]]
Input: board = [["X"]]
Output: [["X"]]
Complexity
Time: O(m * n) Space: O(m * n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Binary Tree Zigzag Level Order TraversalMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM