DSA-099 · Certify boundary-connected open cells, then capture the complement

Surrounded Regions

Core · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 3393 deterministic checks. Learner drafts are not executed.

Understand the problem

Change every O region that has no orthogonal O path to the board boundary into X. Mutate the board in place and return the same outer array.

The board is nonnull and rectangular with nonnull rows, at most 100,000 rows and 100,000 cells. Size bounds are preconditions; null outer input throws NullPointerException and null/ragged rows throw IllegalArgumentException. Zero rows or zero columns are allowed.
Cells are exactly O or X. Reject other symbols and reject shared row objects before any write; every source row must be distinct, including zero-length rows. Null/ragged rows also throw IllegalArgumentException.
Only up/right/down/left O connectivity reaches a boundary. Preserve the outer array and every row object; change precisely unsafe O cells to X. Empty, zero-column, single-row and single-column boards are valid; all O cells on a one-dimensional board already touch a boundary.

Examples

Input: [XXXX,XOOX,XXOX,XOXX]
Output: [XXXX,XXXX,XXXX,XOXX]
The three upper interior O cells are enclosed; the bottom O is a boundary seed.
Input: [XOXX,XOOX,XXOX,XXXX]
Output: unchanged board
The interior component has an O path to the top boundary even though most of it is not itself on the edge.

Before you start

Boundary reachability and connected components
In-place ownership validation versus separate safety state

Recognize the structure

Testing escape independently from each O repeats work. Instead certify all O cells reachable from any boundary O, then capture exactly the remaining open cells. The question asks for the complement of a reachability set.

Try before revealing

Hint 1

Which O cells are definitely not surrounded?

Hint 2

Start from all boundary O cells and mark everything they can reach.

Hint 3

After that traversal, change exactly the remaining O cells to X.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Test escape separately from each O

For each original O, run a BFS through original O cells and record whether any boundary coordinate can be reached. Store all flip decisions before painting so an earlier mutation cannot alter a later escape test. The main method shares one boundary-seeded traversal across the entire board.

Improve the baseline

Validate before mutation

Check every symbol, row shape and row identity. Use a separate safe matrix so no temporary marker changes source letters while reachability is being decided.

Seed the complete boundary once

Scan row-major and enqueue each O lying on any board edge. Combined boundary conditions seed corners once. Propagate safe marks through only O neighbors.

Capture only after certification completes

When the frontier empties, scan all cells and change O to X exactly where safe is false. Return the same board and preserve every row reference.

Why it is correct

Safe marks are justified

Each seed is an O on the boundary; each later safe mark extends an orthogonal O path from a safe coordinate. Every marked cell therefore has an escape path.

Every escaping O is marked

Follow any O path from a boundary seed to an escaping cell. BFS eventually expands each predecessor and claims the next cell, so no escaping cell is omitted.

Complement equals surrounded regions

An O without a boundary path belongs to a closed interior component and must be captured. All other O cells are safe. Delaying writes until this set is complete makes each flip decision refer to the original board.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.*;
public final class Solution {
    private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
    private static int validate(char[][] board) {
        Objects.requireNonNull(board,"board");int columns=board.length==0?0:board[0]==null?-1:board[0].length;
        Set<char[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
        for(char[] row:board){if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");for(char cell:row)if(cell!='O'&&cell!='X')throw new IllegalArgumentException("invalid cell");}
        return columns;
    }
    public static char[][] capture(char[][] board) {
        int columns=validate(board);boolean[][] safe=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
        for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if((r==0||r==board.length-1||c==0||c==columns-1)&&board[r][c]=='O') {safe[r][c]=true;queue.addLast(new int[]{r,c});}
        while(!queue.isEmpty()) {
            int[] cell=queue.removeFirst();
            for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=board.length||nc<0||nc>=columns||board[nr][nc]!='O'||safe[nr][nc])continue;safe[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
        }
        for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O'&&!safe[r][c])board[r][c]='X';
        return board;
    }
    public static char[][] baseline(char[][] board) {
        int columns=validate(board);boolean[][] flip=new boolean[board.length][columns];
        for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O') {
            boolean[][] visited=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean escapes=false;
            while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(cell[0]==0||cell[0]==board.length-1||cell[1]==0||cell[1]==columns-1){escapes=true;break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<columns&&board[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
            flip[r][c]=!escapes;
        }
        for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(flip[r][c])board[r][c]='X';return board;
    }
}

Read the meaningful blocks

Safe is not just on-boundary

An interior cell can be safe through a long O chain.

Distinct row ownership is part of in-place semantics

Aliased rows can make one capture write alter another coordinate; the method rejects this before even an empty/no-change return.

Do not mutate while independent escape tests are pending

The baseline retains decisions separately; the main method finishes the shared safety traversal first.

Complexity

Let R be row count, B total cells, and N=R+B, so validation/row allocation still count when rows have zero columns. Validation, boundary scan, BFS and capture sweep take O(N) time. The safety matrix, queue and row-identity set use O(N) auxiliary space; returned output reuses the original board.

Per-O escape testing can take O(N(B+1)) time and O(N) peak workspace. Its stored decisions are necessary to keep tests based on the original board until the final sweep.

Exact-state walkthroughs

Reveal normal and boundary traces

Boundary certification precedes capture

Input: ["XXXX","XOOX","XXOX","XOXX"] · Captured board view: ["XXXX","XXXX","XXXX","XOXX"]

Step 1 of 7: Seed every boundary O once.

Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.

Surrounded regions — boundary safety before capture

Phase: seed.

Current mutable grid

XXXX

XOOX

XXOX

XO✓XX

Coordinate queue — front at left; already claimed

(3, 1)

✓ = O certified connected to a boundary O. A diagonal is insufficient. The marking phase leaves letters unchanged; the final sweep captures precisely the uncertified O cells. Java changes cell values while preserving the board and its row identities.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`["XXXX","XOOX","XXOX","XOXX"]`
grid	`[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]`
queue	`[[3,1]]`
safe	`[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(char[][] board) {
 5         Objects.requireNonNull(board,"board");int columns=board.length==0?0:board[0]==null?-1:board[0].length;
 6         Set<char[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(char[] row:board){if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");for(char cell:row)if(cell!='O'&&cell!='X')throw new IllegalArgumentException("invalid cell");}
 8         return columns;
 9     }
10     public static char[][] capture(char[][] board) {
11         int columns=validate(board);boolean[][] safe=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
12         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if((r==0||r==board.length-1||c==0||c==columns-1)&&board[r][c]=='O') {safe[r][c]=true;queue.addLast(new int[]{r,c});}
13         while(!queue.isEmpty()) {
14             int[] cell=queue.removeFirst();
15             for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=board.length||nc<0||nc>=columns||board[nr][nc]!='O'||safe[nr][nc])continue;safe[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
16         }
17         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O'&&!safe[r][c])board[r][c]='X';
18         return board;
19     }
20     public static char[][] baseline(char[][] board) {
21         int columns=validate(board);boolean[][] flip=new boolean[board.length][columns];
22         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O') {
23             boolean[][] visited=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean escapes=false;
24             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(cell[0]==0||cell[0]==board.length-1||cell[1]==0||cell[1]==columns-1){escapes=true;break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<columns&&board[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
25             flip[r][c]=!escapes;
26         }
27         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(flip[r][c])board[r][c]='X';return board;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed every boundary O once.
Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
queue
[[3,1]]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"seed"
current
null
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
queue
[]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"visit"
current
[3,1]
Capture one uncertified interior O.
After boundary reachability is complete, precisely the remaining O components are surrounded.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","X","O","X"],["X","X","O","X"],["X","O","X","X"]]
queue
[]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"capture"
current
[1,1]
Capture one uncertified interior O.
After boundary reachability is complete, precisely the remaining O components are surrounded.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","X","X","X"],["X","X","O","X"],["X","O","X","X"]]
queue
[]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"capture"
current
[1,2]
Capture one uncertified interior O.
After boundary reachability is complete, precisely the remaining O components are surrounded.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
queue
[]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"capture"
current
[2,2]
Return the same board after the final sweep.
Java preserves the outer array and each distinct original row object; only selected cell values change.
source
["XXXX","XOOX","XXOX","XOXX"]
grid
[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
queue
[]
safe
[[false,false,false,false],[false,false,false,false],[false,false,false,false],[false,true,false,false]]
phase
"complete"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
["XXXX","XXXX","XXXX","XOXX"]

A long interior escape chain remains safe

Input: ["XOXX","XOOX","XXOX","XXXX"] · Captured board view: ["XOXX","XOOX","XXOX","XXXX"]

Step 1 of 10: Seed every boundary O once.

Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.

Surrounded regions — boundary safety before capture

Phase: seed.

Current mutable grid

XO✓XX

XOOX

XXOX

XXXX

Coordinate queue — front at left; already claimed

(0, 1)

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`["XOXX","XOOX","XXOX","XXXX"]`
grid	`[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]`
queue	`[[0,1]]`
safe	`[[false,true,false,false],[false,false,false,false],[false,false,false,false],[false,false,false,false]]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(char[][] board) {
 5         Objects.requireNonNull(board,"board");int columns=board.length==0?0:board[0]==null?-1:board[0].length;
 6         Set<char[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(char[] row:board){if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");for(char cell:row)if(cell!='O'&&cell!='X')throw new IllegalArgumentException("invalid cell");}
 8         return columns;
 9     }
10     public static char[][] capture(char[][] board) {
11         int columns=validate(board);boolean[][] safe=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
12         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if((r==0||r==board.length-1||c==0||c==columns-1)&&board[r][c]=='O') {safe[r][c]=true;queue.addLast(new int[]{r,c});}
13         while(!queue.isEmpty()) {
14             int[] cell=queue.removeFirst();
15             for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=board.length||nc<0||nc>=columns||board[nr][nc]!='O'||safe[nr][nc])continue;safe[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
16         }
17         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O'&&!safe[r][c])board[r][c]='X';
18         return board;
19     }
20     public static char[][] baseline(char[][] board) {
21         int columns=validate(board);boolean[][] flip=new boolean[board.length][columns];
22         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O') {
23             boolean[][] visited=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean escapes=false;
24             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(cell[0]==0||cell[0]==board.length-1||cell[1]==0||cell[1]==columns-1){escapes=true;break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<columns&&board[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
25             flip[r][c]=!escapes;
26         }
27         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(flip[r][c])board[r][c]='X';return board;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed every boundary O once.
Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[[0,1]]
safe
[[false,true,false,false],[false,false,false,false],[false,false,false,false],[false,false,false,false]]
phase
"seed"
current
null
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[]
safe
[[false,true,false,false],[false,false,false,false],[false,false,false,false],[false,false,false,false]]
phase
"visit"
current
[0,1]
Certify another O as boundary-connected.
Every safe claim has an orthogonal chain of O cells to a boundary seed.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[[1,1]]
safe
[[false,true,false,false],[false,true,false,false],[false,false,false,false],[false,false,false,false]]
phase
"claim"
current
[0,1]
claimed
[1,1]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[]
safe
[[false,true,false,false],[false,true,false,false],[false,false,false,false],[false,false,false,false]]
phase
"visit"
current
[1,1]
Certify another O as boundary-connected.
Every safe claim has an orthogonal chain of O cells to a boundary seed.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[[1,2]]
safe
[[false,true,false,false],[false,true,true,false],[false,false,false,false],[false,false,false,false]]
phase
"claim"
current
[1,1]
claimed
[1,2]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[]
safe
[[false,true,false,false],[false,true,true,false],[false,false,false,false],[false,false,false,false]]
phase
"visit"
current
[1,2]
Certify another O as boundary-connected.
Every safe claim has an orthogonal chain of O cells to a boundary seed.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[[2,2]]
safe
[[false,true,false,false],[false,true,true,false],[false,false,true,false],[false,false,false,false]]
phase
"claim"
current
[1,2]
claimed
[2,2]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[]
safe
[[false,true,false,false],[false,true,true,false],[false,false,true,false],[false,false,false,false]]
phase
"visit"
current
[2,2]
Return the same board after the final sweep.
Java preserves the outer array and each distinct original row object; only selected cell values change.
source
["XOXX","XOOX","XXOX","XXXX"]
grid
[["X","O","X","X"],["X","O","O","X"],["X","X","O","X"],["X","X","X","X"]]
queue
[]
safe
[[false,true,false,false],[false,true,true,false],[false,false,true,false],[false,false,false,false]]
phase
"complete"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
["XOXX","XOOX","XXOX","XXXX"]

A single row is entirely boundary

Input: ["OOXOO"] · Captured board view: ["OOXOO"]

Step 1 of 7: Seed every boundary O once.

Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.

Surrounded regions — boundary safety before capture

Phase: seed.

Current mutable grid

O✓O✓XO✓O✓

Coordinate queue — front at left; already claimed

(0, 0)
(0, 1)
(0, 3)
(0, 4)

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`["OOXOO"]`
grid	`[["O","O","X","O","O"]]`
queue	`[[0,0],[0,1],[0,3],[0,4]]`
safe	`[[true,true,false,true,true]]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(char[][] board) {
 5         Objects.requireNonNull(board,"board");int columns=board.length==0?0:board[0]==null?-1:board[0].length;
 6         Set<char[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(char[] row:board){if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");for(char cell:row)if(cell!='O'&&cell!='X')throw new IllegalArgumentException("invalid cell");}
 8         return columns;
 9     }
10     public static char[][] capture(char[][] board) {
11         int columns=validate(board);boolean[][] safe=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
12         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if((r==0||r==board.length-1||c==0||c==columns-1)&&board[r][c]=='O') {safe[r][c]=true;queue.addLast(new int[]{r,c});}
13         while(!queue.isEmpty()) {
14             int[] cell=queue.removeFirst();
15             for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=board.length||nc<0||nc>=columns||board[nr][nc]!='O'||safe[nr][nc])continue;safe[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
16         }
17         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O'&&!safe[r][c])board[r][c]='X';
18         return board;
19     }
20     public static char[][] baseline(char[][] board) {
21         int columns=validate(board);boolean[][] flip=new boolean[board.length][columns];
22         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O') {
23             boolean[][] visited=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean escapes=false;
24             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(cell[0]==0||cell[0]==board.length-1||cell[1]==0||cell[1]==columns-1){escapes=true;break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<columns&&board[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
25             flip[r][c]=!escapes;
26         }
27         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(flip[r][c])board[r][c]='X';return board;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed every boundary O once.
Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[[0,0],[0,1],[0,3],[0,4]]
safe
[[true,true,false,true,true]]
phase
"seed"
current
null
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[[0,1],[0,3],[0,4]]
safe
[[true,true,false,true,true]]
phase
"visit"
current
[0,0]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[[0,3],[0,4]]
safe
[[true,true,false,true,true]]
phase
"visit"
current
[0,1]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[[0,4]]
safe
[[true,true,false,true,true]]
phase
"visit"
current
[0,3]
Expand one boundary-connected coordinate.
Boundary connectivity is computed before any O is changed to X.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[]
safe
[[true,true,false,true,true]]
phase
"visit"
current
[0,4]
Return the same board after the final sweep.
Java preserves the outer array and each distinct original row object; only selected cell values change.
source
["OOXOO"]
grid
[["O","O","X","O","O"]]
queue
[]
safe
[[true,true,false,true,true]]
phase
"complete"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
["OOXOO"]

Empty board

Input: [] · Captured board view: []

Step 1 of 3: Seed every boundary O once.

Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.

Surrounded regions — boundary safety before capture

Phase: seed.

Current mutable grid

No cells.

Coordinate queue — front at left; already claimed

Empty.

The exact state table and static walkthrough below provide the same information without relying on color.

State after this step
Variable	Value
source	`[]`
grid	`[]`
queue	`[]`
safe	`[]`
phase	`"seed"`
current	`null`

See the affected Java block

 1 import java.util.*;
 2 public final class Solution {
 3     private static final int[][] DIRECTIONS = {{-1,0},{0,1},{1,0},{0,-1}};
 4     private static int validate(char[][] board) {
 5         Objects.requireNonNull(board,"board");int columns=board.length==0?0:board[0]==null?-1:board[0].length;
 6         Set<char[]> rows=Collections.newSetFromMap(new IdentityHashMap<>());
 7         for(char[] row:board){if(row==null||row.length!=columns||!rows.add(row))throw new IllegalArgumentException("nonrectangular or aliased rows");for(char cell:row)if(cell!='O'&&cell!='X')throw new IllegalArgumentException("invalid cell");}
 8         return columns;
 9     }
10     public static char[][] capture(char[][] board) {
11         int columns=validate(board);boolean[][] safe=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();
12         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if((r==0||r==board.length-1||c==0||c==columns-1)&&board[r][c]=='O') {safe[r][c]=true;queue.addLast(new int[]{r,c});}
13         while(!queue.isEmpty()) {
14             int[] cell=queue.removeFirst();
15             for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr<0||nr>=board.length||nc<0||nc>=columns||board[nr][nc]!='O'||safe[nr][nc])continue;safe[nr][nc]=true;queue.addLast(new int[]{nr,nc});}
16         }
17         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O'&&!safe[r][c])board[r][c]='X';
18         return board;
19     }
20     public static char[][] baseline(char[][] board) {
21         int columns=validate(board);boolean[][] flip=new boolean[board.length][columns];
22         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(board[r][c]=='O') {
23             boolean[][] visited=new boolean[board.length][columns];ArrayDeque<int[]> queue=new ArrayDeque<>();visited[r][c]=true;queue.addLast(new int[]{r,c});boolean escapes=false;
24             while(!queue.isEmpty()){int[] cell=queue.removeFirst();if(cell[0]==0||cell[0]==board.length-1||cell[1]==0||cell[1]==columns-1){escapes=true;break;}for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<board.length&&nc>=0&&nc<columns&&board[nr][nc]=='O'&&!visited[nr][nc]){visited[nr][nc]=true;queue.addLast(new int[]{nr,nc});}}}
25             flip[r][c]=!escapes;
26         }
27         for(int r=0;r<board.length;r++)for(int c=0;c<columns;c++)if(flip[r][c])board[r][c]='X';return board;
28     }
29 }
30

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed every boundary O once.
Safe means connected to a boundary O, not merely adjacent to any boundary. Source letters stay unchanged during this marking phase.
source
[]
grid
[]
queue
[]
safe
[]
phase
"seed"
current
null
Return the same board after the final sweep.
Java preserves the outer array and each distinct original row object; only selected cell values change.
source
[]
grid
[]
queue
[]
safe
[]
phase
"complete"
current
null
Return the documented value, changed-grid view, fresh result, or cloned graph view.
Coordinates and object identities follow the problem-specific contract. Discovery histories are teaching views, not additional Java workspace.
result
[]

Test the contract

Input: Empty/zero-column board
Output: same unchanged board
No capturable cells.
Input: Single row or column
Output: all original O preserved
Every O lies on a boundary.
Input: Interior connected to boundary O
Output: preserved
Reachability, not local position.
Input: Large closed interior
Output: all enclosed O become X
Linear certification plus sweep.

Common mistakes and counterexamples

Capture every interior O

Counterexample: Interior cells may connect to a distant boundary O.

Compute connectivity, not just coordinate position.

Use diagonal escape

Counterexample: A corner touch through X does not form an orthogonal O path.

Use the four declared directions.

Start captures before safety is complete

Counterexample: Changing a connecting O can destroy the evidence of an original escape path.

Finish boundary marking before writing any capture.

Follow-ups

Allow diagonal escape.

Change the adjacency relation to eight directions and revise the safe set. Boundary seeding is unchanged but diagonal-only examples now differ.

Return a fresh board instead.

Allow aliased source rows because you no longer write them, and allocate independent output rows. Mutation and output ownership change, not the reachability proof.

Return region counts or areas.

After safety marking, traverse the unsafe components separately to count or measure them before capture. Distinguish a cell total from the number of enclosed components.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 166/20,000 characters

Self-review

Can I prove both directions of the safe-set characterization?Can I explain why the complement is exactly the capture set?Can I preserve input row identities while making only authorized cell writes?

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Standard names do not imply company-frequency or external-platform equivalence claims.