How should I practice Capture Surrounded Regions with Union-Find?

Start by reading the full statement, solve the visible examples, then compare the pattern against related Apple phone screen problems in FastPrep.

Is Capture Surrounded Regions with Union-Find associated with Apple?

FastPrep tags this as a Apple phone screen coding practice problem when the problem catalog has that company and stage context.

Capture Surrounded Regions with Union-Find

Apple● MediumFULLTIMEPHONE SCREEN

Problem statement

You are given a rectangular board as an array of equal-length strings board. Every character is either X or O.

A group consists of O cells connected through shared sides. Diagonal contact does not connect cells. A group is surrounded if none of its cells touches the outer edge of the board: the first or last row or column.

Replace every O in a surrounded group with X. Preserve all other characters and return the resulting row strings in the original row order. Do not change the input array.

Implement and use a disjoint-set union data structure, also called union-find. Do not solve the board with depth-first search or breadth-first search.

Function

captureSurroundedRegions(board: String[]) → String[]

Examples

Example 1

board = ["XXXX","XOOX","XXOX","XOXX"]return = ["XXXX","XXXX","XXXX","XOXX"]

The three connected interior O cells cannot reach a border and become X. The bottom-row O already touches the border and is preserved.

Example 2

board = ["OOOO","OXXO","OXOO"]return = ["OOOO","OXXO","OXOO"]

Every O belongs to a component that touches an outer row or column, so the board is unchanged.

Example 3

board = ["OXX","XOX","XXO"]return = ["OXX","XXX","XXO"]

Diagonal contact does not connect components. The center O is surrounded, while the two corner cells are on the border.

Constraints

1 <= board.length <= 200.
1 <= board[r].length <= 200 for every row r.
All rows have the same length.
Every character is the ASCII letter X or O.