Surrounded Regions

MEDIUM✓ CHIP-TIMEDLC #130 — FULL STATEMENT ↗

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.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

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.

EX 01

board = ["XX", "XX"]

→ ["XX", "XX"]

NO O'S AT ALL

EX 02

board = ["XXX", "XOX", "XXX"]

→ ["XXX", "XXX", "XXX"]

SINGLE FULLY ENCLOSED O

EX 03

board = ["OXX", "XXX", "XXX"]

→ ["OXX", "XXX", "XXX"]

O SITS DIRECTLY ON THE BORDER

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 HINTS — TAKE 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 BOARD — THE PATTERN, STEP BY STEP

THE BORDER-FIRST FLOODPATTERN · FLOOD FROM THE BORDER FIRSTboard 4×5 · one region captured, one escapes

STEP 1

Scan every border cell first — any O touching the edge, directly or through a chain, survives. Everything else gets captured.

STEP 1 / 6 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/surrounded-regions.py — RACE PACE

LANG ▸

PACE ▸

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'

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · RACE PACE · 30 LN

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'

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)PYTHON · TRAINING PACE · 25 LN

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});
                }
            }
        }
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · RACE PACE · 37 LN

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';
                    }
                }
            }
        }
    }
}

TIME O(ROWS·COLS)SPACE O(ROWS·COLS)JAVA · TRAINING PACE · 35 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED