The O(n) Club: Surrounded Regions — Don’t Flip Out, Mark the Borders!

The O(n) Club: Surrounded Regions — Don’t Flip Out, Mark the Borders!

⚡ TL;DR

Got a board of ‘O’s and ‘X’s? Flip every ‘O’ that’s completely surrounded by ‘X’s into an ‘X’—unless it or its buddies touch the border. Basically: Don’t be that junior dev who reboots the server before checking the cables.

// BAD: naïve blast radius
for (int i = 1; i < rows-1; i++)
  for (int j = 1; j < cols-1; j++)
    if (board[i][j] == 'O') board[i][j] = 'X';
// Border-connected 'O's get unfairly nuked!

🧠 How Devs Usually Mess This Up

The default rookie move: flip every interior ‘O’. But if it’s even remotely connected to a border ‘O’ (like a VPN to freedom), you’re going to accidentally flatten survivors who should live. Boards don’t forgive; neither do test cases.

🔍 What’s Actually Going On

Think of the board like a game of Go: you only capture a group if it is totally trapped. The border is their secret tunnel out of prison. Any ‘O’ connected (even through a messy pipeline of fellow ‘O’s) is safe—treat it like it has diplomatic immunity. The real play: Identify and mark everyone with border connections before you start flipping the doomed ones.

🛠️ PseudoCode

• Walk every border cell. When you find an ‘O’, launch your DFS/BFS like a security drone marking all connected ‘O’s with a special marker (say, ‘T’).

  // For each border cell:
  if (cell == 'O') markAsSafe(cell); // DFS or BFS

• Now, sweep the whole board.
  

  for (each cell)
    if (cell == 'O') cell = 'X';        // Flip losers
    else if (cell == 'T') cell = 'O';   // Restore winners
  

  The survivors get a stay of execution.

💻 The Code

public void solve(char[][] board) {
    int rows = board.length;
    if (rows == 0) return;
    int cols = board[0].length;
    // Mark border-connected O's as 'T'
    for (int i = 0; i < rows; i++) {
        if (board[i][0] == 'O') mark(board, i, 0);
        if (board[i][cols - 1] == 'O') mark(board, i, cols - 1);
    }
    for (int j = 0; j < cols; j++) {
        if (board[0][j] == 'O') mark(board, 0, j);
        if (board[rows - 1][j] == 'O') mark(board, rows - 1, j);
    }
    // Flip & unflip
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (board[i][j] == 'O') board[i][j] = 'X';
            if (board[i][j] == 'T') board[i][j] = 'O';
        }
    }
}
private void mark(char[][] board, int row, int col) {
    if (row < 0 || col < 0 || row >= board.length || col >= board[0].length) return;
    if (board[row][col] != 'O') return;
    board[row][col] = 'T';
    mark(board, row+1, col);
    mark(board, row-1, col);
    mark(board, row, col+1);
    mark(board, row, col-1);
}

⚠️ Pitfalls, Traps & Runtime Smacks

• Check all four borders—one skipped edge and your ‘O’s escape (or worse, get wrongfully axed).
• Recursion can stack overflow on monster boards—swap to BFS if your call stack has stage fright.
• Try test grids where ‘O’s snake from border to deep inside: they should never flip. Test like an evil QA.
• Runs in O(mn) time, uses only the grid for extra space (unless Java’s stack says “nope”).

🧠 Interviewer Brain-Tattoo

“Always check who’s got a route to the border before swinging your algorithmic sword. Not every ‘O’ is truly surrounded—just mostly harassed.”