Capture Enclosed O Regions in an X/O Grid Using Union-Find Instead of Flood Fill

You are given an m × n board in which every cell is 'X' or 'O'. Two 'O' cells are connected when they share an edge (up, down, left or right), and a region is a maximal group of connected 'O' cells. A region is enclosed when none of its cells lies on the outer border of the board, that is, in the first or last row or the first or last column. Every cell of an enclosed region is captured and becomes 'X'; regions with at least one border cell stay as they are.

Return the board after every enclosed region has been captured.

In the interview, this was solved with a disjoint-set (union-find) structure: a skeleton with find and union was provided to complete, and depth-first or breadth-first flood fill was not allowed. Practice it the same way; the grader checks only the returned board.

Function Signature

def capture_enclosed_regions(board: list[list[str]]) -> list[list[str]]:

Rules

• Connectivity is 4-directional; cells that touch only diagonally are not connected.
• 'X' cells never change, and an 'O' cell changes only if its whole region is enclosed.
• A board with one row or one column has every cell on the border, so it is returned unchanged.
• You may modify board in place, but you must return the resulting board, with the same dimensions as the input.

Constraints

• 1 <= m, n <= 200, where m = len(board) and n = len(board[0])
• Every row has exactly n cells
• Every cell is the one-character string 'X' or 'O'

Examples

Example 1

Input: board = [["X","X","X","X","X"],
 ["X","O","O","X","X"],
 ["X","X","O","X","O"],
 ["X","O","X","X","X"]]
Output: [["X","X","X","X","X"],
 ["X","X","X","X","X"],
 ["X","X","X","X","O"],
 ["X","O","X","X","X"]]

The region (1, 1), (1, 2), (2, 2) has no border cell, so it is captured. The cell (2, 4) is in the last column and (3, 1) is in the last row, so both stay.

Example 2

Input: board = [["O","X","X"],
 ["X","O","X"],
 ["X","X","X"]]
Output: [["O","X","X"],
 ["X","X","X"],
 ["X","X","X"]]

The cell (1, 1) touches (0, 0) only diagonally, so it forms its own enclosed region and is captured. The cell (0, 0) is on the border and stays.

Example 3

Input: board = [["X","X","X","X","X"],
 ["X","O","O","O","X"],
 ["X","O","X","O","X"],
 ["X","O","O","O","X"],
 ["X","X","X","O","X"]]
Output: [["X","X","X","X","X"],
 ["X","O","O","O","X"],
 ["X","O","X","O","X"],
 ["X","O","O","O","X"],
 ["X","X","X","O","X"]]

The ring of 'O' cells is one region, and it reaches the bottom row through (4, 3), so the whole ring stays even though most of its cells are interior.