DSA interview question

Surrounded Regions

Medium · Data structures · Topics: graph, dfs, bfs, matrix

The problem

In a Go-like board game, a region of 'O' cells is captured (flipped to 'X') if it's completely surrounded by 'X', meaning it can't reach the border of the board through 'O' cells. Checking each region's escape route separately is wasteful. Flip the logic: every 'O' region that touches the border is safe, so flood-fill from all border 'O's and mark them. Every 'O' left unmarked is captured.

Example: XXXX / XOOX / XXOX / XOXX → XXXX / XXXX / XXXX / XOXX.

Function signature

void solve(vector<string>& board);  // in place

Test cases

Input (rows)	Output (rows)	Explanation
`XXXX XOOX XXOX XOXX`	`XXXX XXXX XXXX XOXX`	The bottom O touches the border
`XXX XOX XXX`	`XXX XXX XXX`	A single enclosed O
`OOO OXO OOO`	`OOO OXO OOO`	Everything touches the border
`X`	`X`
`O`	`O`	A border cell is safe

(Confirm: connectivity is 4-directional; O cells on the border, or connected to one, are never captured.)

How interviewers phrase it

"Capture all regions that are 4-directionally surrounded by 'X' by flipping their 'O's to 'X'" (LeetCode 130).

Clarifying questions to ask

4-directional? (Yes.)
Are border O's ever captured? (No.)
In place? (Yes.)

Follow-ups to expect

"Why start from the border?"
"How do you mark without extra memory?"
"DSU alternative?"
"Why BFS instead of recursive DFS?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview