Surrounded Regions
The briefingthe full drill, in my own words
The drill: In a grid of 'X' and 'O', flip every 'O' to 'X' unless it belongs to a group of connected O's that touches the border — those escape untouched, everything fully enclosed gets captured.
A board of 'X' and 'O' characters holds regions of connected O's. Any region of O's that touches the border of the board — directly or through a chain of other O's — is safe; every other region is fully enclosed and gets flipped to X.
The flip happens in place, on the same board that was passed in — there's no separate structure to build up and return, just the board with every captured region converted.
A single O sitting on the border counts as touching it, and that safety spreads to every O connected to it, no matter how deep into the board that connected group reaches.
- board up to a couple hundred cells per side
- cells hold exactly 'X' or 'O'
- connectivity for a region is 4-directional
- any O connected to a border O, even indirectly, stays untouched
The hintstake only what you need
HINT 1 THE NUDGE
A region of O's survives only if some path of O's inside it reaches the edge of the board — otherwise every O in it gets flipped. Checking each region in isolation for 'does it touch a wall' works, but it repeats a lot of exploring.
HINT 2 THE STRUCTURE
Flip the question: instead of asking which regions are enclosed, mark which O's are safe by flood-filling inward from the border first — everything the border-flood never reaches was enclosed all along.
HINT 3 ONE STEP FROM THE ANSWER
Flood-fill from every border 'O' first, marking each one reached with a temporary marker, then make one final pass over the whole board: any remaining 'O' becomes 'X', and every marked cell reverts back to 'O'.
Coach's boardthe pattern, step by step
Scan every border cell first — any O touching the edge, directly or through a chain, survives. Everything else gets captured.
The splitstwo paces, two languages
class Solution:
def solve(self, board: List[List[str]]) -> None:
rows, cols = len(board), len(board[0])
def flood(r, c):
stack = [(r, c)]
board[r][c] = 'S'
while stack:
cr, cc = stack.pop()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O':
board[nr][nc] = 'S'
stack.append((nr, nc))
for r in range(rows):
for c in (0, cols - 1):
if board[r][c] == 'O':
flood(r, c)
for c in range(cols):
for r in (0, rows - 1):
if board[r][c] == 'O':
flood(r, c)
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O':
board[r][c] = 'X'
elif board[r][c] == 'S':
board[r][c] = 'O'class Solution:
def solve(self, board: List[List[str]]) -> None:
rows, cols = len(board), len(board[0])
visited = [[False] * cols for _ in range(rows)]
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O' and not visited[r][c]:
region = []
touches_border = False
stack = [(r, c)]
visited[r][c] = True
while stack:
cr, cc = stack.pop()
region.append((cr, cc))
if cr == 0 or cr == rows - 1 or cc == 0 or cc == cols - 1:
touches_border = True
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < rows and 0 <= nc < cols and board[nr][nc] == 'O' and not visited[nr][nc]:
visited[nr][nc] = True
stack.append((nr, nc))
if not touches_border:
for cr, cc in region:
board[cr][cc] = 'X'class Solution {
public void solve(char[][] board) {
int rows = board.length, cols = board[0].length;
for (int r = 0; r < rows; r++) {
if (board[r][0] == 'O') flood(board, r, 0);
if (board[r][cols - 1] == 'O') flood(board, r, cols - 1);
}
for (int c = 0; c < cols; c++) {
if (board[0][c] == 'O') flood(board, 0, c);
if (board[rows - 1][c] == 'O') flood(board, rows - 1, c);
}
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 'O') board[r][c] = 'X';
else if (board[r][c] == 'S') board[r][c] = 'O';
}
}
}
private void flood(char[][] board, int r, int c) {
int rows = board.length, cols = board[0].length;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
board[r][c] = 'S';
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!stack.isEmpty()) {
int[] cur = stack.pop();
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == 'O') {
board[nr][nc] = 'S';
stack.push(new int[]{nr, nc});
}
}
}
}
}class Solution {
public void solve(char[][] board) {
int rows = board.length, cols = board[0].length;
boolean[][] visited = new boolean[rows][cols];
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 'O' && !visited[r][c]) {
List<int[]> region = new ArrayList<>();
boolean touchesBorder = false;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{r, c});
visited[r][c] = true;
while (!stack.isEmpty()) {
int[] cur = stack.pop();
region.add(cur);
if (cur[0] == 0 || cur[0] == rows - 1 || cur[1] == 0 || cur[1] == cols - 1) {
touchesBorder = true;
}
for (int[] d : dirs) {
int nr = cur[0] + d[0], nc = cur[1] + d[1];
if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && board[nr][nc] == 'O' && !visited[nr][nc]) {
visited[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
if (!touchesBorder) {
for (int[] cell : region) board[cell[0]][cell[1]] = 'X';
}
}
}
}
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED