Surrounded Regions: Why You Should Flood Fill From the Border
Surrounded Regions asks you to flip every 'O' that is completely enclosed by 'X' on a 2D board. The trick that makes it easy is to reverse the question.
Reverse the question
Instead of asking which regions are surrounded, ask which 'O' cells can escape. An 'O' survives only if it is connected to an 'O' on the border. So run a flood fill from every border 'O', mark those cells as safe, and then flip everything else.
Code (Python, iterative BFS)
from collections import deque
def solve(board):
if not board: return
m, n = len(board), len(board[0])
q = deque((r, c) for r in range(m) for c in range(n)
if (r in (0, m-1) or c in (0, n-1)) and board[r][c] == 'O')
while q:
r, c = q.popleft()
if 0 <= r < m and 0 <= c < n and board[r][c] == 'O':
board[r][c] = 'S'
q.extend([(r+1, c), (r-1, c), (r, c+1), (r, c-1)])
for r in range(m):
for c in range(n):
board[r][c] = 'O' if board[r][c] == 'S' else 'X'
Every cell is visited a constant number of times, so time is O(m*n). BFS avoids the recursion depth problems a recursive DFS hits on a 200x200 board, which is worth mentioning.
Alternatives and follow-ups
Union-find with a virtual border node also works and is a good answer if the interviewer asks for one. Related problems: Number of Enclaves (count instead of flip) and Pacific Atlantic Water Flow (two border sources).
Communicating it
Say the reversal first, because it is the whole insight. Then mention the marker character trick that avoids an extra visited matrix. If you want an AI interview copilot that nudges you toward these reframes in practice sessions, that is what we build at Linkjob AI (disclosure: I am on the team).