Surrounded Regions

Given a board of 'X' and 'O' cells stored as a char[][] (a char is one 16-bit character; a String is immutable, so each row is converted with toCharArray to allow in-place edits), capture every region of 'O's that is completely surrounded by 'X's by flipping it to 'X'. A region is a group of 'O's connected horizontally or vertically. A region that touches the border of the board isn't surrounded and stays as it is.

LeetCode: 130. Surrounded Regions

Example

Text

Input:        Output:
X X X X       X X X X
X O O X       X X X X
X X O X       X X X X
X O X X       X O X X

The bottom O is on the border, so it stays. The other three are enclosed.

Brute force: search from every O

For each 'O', search its region to see whether it reaches the border. If it doesn't, the cell is captured. Decisions are made on the original board and applied afterwards, so earlier flips don't affect later searches.

Java

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class Main {
    static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
    static char[][] toBoard(String... rows) {
        char[][] board = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) board[i] = rows[i].toCharArray();
        return board;
    }

    static boolean reachesBorder(char[][] board, int sr, int sc) {
        int rows = board.length, cols = board[0].length;
        boolean[][] seen = new boolean[rows][cols];
        Deque<int[]> stack = new ArrayDeque<>();
        stack.push(new int[]{sr, sc});
        seen[sr][sc] = true;
        while (!stack.isEmpty()) {
            int[] cur = stack.pop();
            int r = cur[0], c = cur[1];
            if (r == 0 || c == 0 || r == rows - 1 || c == cols - 1) {
                return true;
            }
            for (int[] d : DIRS) {
                int nr = r + d[0], nc = c + d[1];
                if (board[nr][nc] == 'O' && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    stack.push(new int[]{nr, nc});
                }
            }
        }
        return false;
    }

    static void solve(char[][] board) {
        List<int[]> captured = new ArrayList<>();
        for (int r = 0; r < board.length; r++) {
            for (int c = 0; c < board[0].length; c++) {
                if (board[r][c] == 'O' && !reachesBorder(board, r, c)) {
                    captured.add(new int[]{r, c});
                }
            }
        }
        for (int[] cell : captured) {
            board[cell[0]][cell[1]] = 'X';
        }
    }

    public static void main(String[] args) {
        char[][] board = toBoard("XXXX", "XOOX", "XXOX", "XOXX");
        solve(board);
        for (char[] row : board) {
            System.out.println(new String(row));
        }
    }
}

Output

XXXX
XXXX
XXXX
XOXX

Time: O((m·n)²): every 'O' may search a region as large as the board. Space: O(m·n).

The neighbor indexes r - 1 and c - 1 cannot be negative, and r + 1 and c + 1 cannot reach the board size, because a cell on the border returns before its neighbors are generated. No ArrayIndexOutOfBoundsException can occur.

Optimal: flood fill from the border

Turn the question around. The cells that survive are exactly the 'O's connected to a border 'O'. So:

Start a flood fill from every 'O' on the border and mark everything it reaches as safe (temporarily 'S').
Scan the board once: remaining 'O's are enclosed and become 'X'; 'S' cells go back to 'O'.

Java

import java.util.ArrayDeque;
import java.util.Deque;

public class Main {
    static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // up, down, left, right
    static char[][] toBoard(String... rows) {
        char[][] board = new char[rows.length][];
        for (int i = 0; i < rows.length; i++) board[i] = rows[i].toCharArray();
        return board;
    }

    static void solve(char[][] board) {
        if (board.length == 0) {
            return;
        }
        int rows = board.length, cols = board[0].length;
        Deque<int[]> stack = new ArrayDeque<>();
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                boolean onBorder = r == 0 || c == 0 || r == rows - 1 || c == cols - 1;
                if (onBorder && board[r][c] == 'O') {
                    board[r][c] = 'S';
                    stack.push(new int[]{r, c});
                }
            }
        }
        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});
                }
            }
        }
        for (char[] row : board) {
            for (int c = 0; c < cols; c++) {
                row[c] = row[c] == 'S' ? 'O' : 'X';
            }
        }
    }

    public static void main(String[] args) {
        char[][] board = toBoard("XXXX", "XOOX", "XXOX", "XOXX");
        solve(board);
        for (char[] row : board) {
            System.out.println(new String(row));
        }

        board = toBoard("OOO", "OXO", "OOO");
        solve(board);
        StringBuilder sb = new StringBuilder();
        for (char[] row : board) {
            if (sb.length() > 0) sb.append(' ');
            sb.append(row);
        }
        System.out.println(sb);
    }
}

Output

XXXX
XXXX
XXXX
XOXX
OOO OXO OOO

Time: O(m·n): each cell is marked at most once. Space: O(m·n) for the stack in the worst case.

The bounds check nr >= 0 && nr < rows && nc >= 0 && nc < cols keeps every neighbor inside the board. An explicit stack (ArrayDeque) instead of recursion keeps a large all-'O' board from throwing StackOverflowError.

Edge cases

Empty board: nothing to do.
Boards with one or two rows or columns: every cell is on the border, so nothing is captured.
Every 'O' connected to the border: nothing changes.