Definition
- Surrounded region – a group of 'O' cells that has no path to any border cell; these are captured by flipping them to 'X'.
- Border-connected 'O' – an 'O' cell that is on the border or reachable from a border 'O' through adjacent 'O' cells; these are safe and remain 'O'.
- Sentinel marking – during the border DFS, mark safe 'O' cells with a temporary character (like 'S') so the final sweep can distinguish them from enclosed 'O' cells.
- Final sweep – iterate the board: any cell still 'O' is enclosed and becomes 'X'; any cell 'S' is safe and restored to 'O'.
- Problem inversion – instead of detecting surrounded regions directly, mark the complement (border-connected cells) and capture everything else.
At the National Bank of India, a compliance grid marks open exposures. An exposure is safe only if it connects to the border of the jurisdiction. Rajesh starts from the border and marks everything connected as protected. Any exposure that is not protected is fully enclosed, so it gets closed.
Understanding the Concepts
What is the Surrounded Regions problem?
The problem gives a board of 'X' and 'O' characters. The task is to capture all regions of 'O' that are completely surrounded by 'X' by flipping them to 'X'. An 'O' on the border or connected to a border 'O' through adjacent 'O' cells is safe and must remain 'O'. Only fully enclosed regions are captured.
package com.bank.service;
public class SurroundedRegions {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int rows = board.length, cols = board[0].length;
// Step 1: mark border-connected O's as safe (S)
for (int r = 0; r < rows; r++) {
if (board[r][0] == 'O') dfs(board, r, 0);
if (board[r][cols - 1] == 'O') dfs(board, r, cols - 1);
}
for (int c = 0; c < cols; c++) {
if (board[0][c] == 'O') dfs(board, 0, c);
if (board[rows - 1][c] == 'O') dfs(board, rows - 1, c);
}
// Step 2: sweep - O becomes X, S becomes O
for (int r = 0; r < rows; r++) {
for (int c = 0; c < cols; c++) {
if (board[r][c] == 'O') board[r][c] = 'X'; // enclosed
else if (board[r][c] == 'S') board[r][c] = 'O'; // safe
}
}
}
private void dfs(char[][] board, int r, int c) {
if (r < 0 || c < 0 || r >= board.length || c >= board[0].length
|| board[r][c] != 'O') return;
board[r][c] = 'S'; // sentinel: safe
dfs(board, r + 1, c);
dfs(board, r - 1, c);
dfs(board, r, c + 1);
dfs(board, r, c - 1);
}
public static void main(String[] args) {
char[][] board = {
{'X', 'X', 'X', 'X'},
{'X', 'O', 'O', 'X'},
{'X', 'X', 'O', 'X'},
{'X', 'O', 'X', 'X'}
};
new SurroundedRegions().solve(board);
for (char[] row : board) {
System.out.println(new String(row));
}
}
}
XXXX
XXXX
XXXX
XOXX
Why invert the problem instead of detecting enclosure directly?
Detecting enclosure directly is awkward because you would need to prove that a region of 'O' cells has no path to any border cell, which requires running a full traversal of each region and checking every cell's border status. Inverting the problem is far cleaner: mark every 'O' reachable from a border 'O' as safe, then capture the complement. This way, you only traverse from border cells and a single sweep captures everything else.
package com.bank.service;
public class InversionExplanation {
// Direct approach: for each O region, check if any cell touches the border
// - Need to track regions separately
// - Complex and error-prone
//
// Inverted approach: mark border-connected O's, flip the rest
// - Only traverse from border cells
// - Single sweep to capture
// - Simple and correct
public static void main(String[] args) {
System.out.println("Inverted approach: mark safe from border, flip the rest.");
}
}
How does the sentinel marking work?
The sentinel character (such as 'S') temporarily replaces border-connected 'O' cells during the DFS phase. This distinguishes them from enclosed 'O' cells that should be captured. During the final sweep, 'O' cells become 'X' (captured) and 'S' cells become 'O' (restored). Using a sentinel avoids the need for a separate visited matrix.
package com.bank.service;
public class SentinelDemo {
public static void main(String[] args) {
// After DFS from border:
// O on border or connected to border -> S (safe)
// O enclosed -> still O
// X -> still X
//
// Final sweep:
// O -> X (capture)
// S -> O (restore)
// X -> X (unchanged)
char[][] board = {
{'X', 'O', 'X'},
{'O', 'O', 'X'},
{'X', 'X', 'X'}
};
// (0,1) is border O -> mark S
// (1,0) is border O -> mark S
// (1,1) connected to border O's -> mark S
// All O's are border-connected, none captured
new SurroundedRegions().solve(board);
for (char[] row : board) System.out.println(new String(row));
}
}
XOX
OOX
XXX
How is this different from Number of Islands and Flood Fill?
| Feature | Number of Islands | Flood Fill | Surrounded Regions |
|---|---|---|---|
| Start | every unvisited land | one specified cell | every border 'O' |
| Goal | count components | recolor one region | capture enclosed regions |
| Marking | visited by overwrite | new color as visited | sentinel then sweep |
| Key insight | flood fill per component | no-op guard | problem inversion |
package com.bank.service;
public class GridProblemsComparison {
public static void main(String[] args) {
System.out.println("Islands: count components via sweep + flood fill.");
System.out.println("Flood Fill: recolor one region from start cell.");
System.out.println("Surrounded Regions: invert, mark border, capture rest.");
}
}
What are the edge cases?
Edge cases include a board with no 'O' cells (nothing to capture), a board where all 'O' cells are on the border (nothing to capture), a board where all 'O' cells are enclosed (all captured), and a 1-row or 1-column board (all cells are border cells, so nothing is captured).
package com.bank.service;
public class SurroundedEdgeCases {
public static void main(String[] args) {
SurroundedRegions solver = new SurroundedRegions();
// All border O's: nothing captured
char[][] allBorder = {
{'O', 'O'},
{'O', 'O'}
};
solver.solve(allBorder);
System.out.println("All border: " + new String(allBorder[0]));
// Single row: all cells are border
char[][] singleRow = {{'X', 'O', 'X', 'O', 'X'}};
solver.solve(singleRow);
System.out.println("Single row: " + new String(singleRow[0]));
}
}
All border: OO
Single row: XOXOX
What are common mistakes?
The most common mistake is trying to detect surrounded regions directly instead of inverting the problem, which leads to complex and buggy code. Another mistake is forgetting to restore sentinel cells back to 'O' in the final sweep. A third mistake is starting DFS from interior cells instead of border cells only.
Wrong approach:
// WRONG: trying to check if each O region is enclosed
// Complex, must track each region and check all cells for border contact
Correct approach:
// CORRECT: invert the problem
// 1. DFS from border O's, mark as sentinel
// 2. Sweep: O -> X, sentinel -> O
Can you solve it with BFS instead of DFS?
Yes. Replace the recursive DFS with a queue-based BFS. Enqueue all border 'O' cells, mark them as 'S', and process the queue by spreading to adjacent 'O' cells. This avoids stack overflow on large boards.
package com.bank.service;
import java.util.LinkedList;
import java.util.Queue;
public class SurroundedRegionsBFS {
public void solve(char[][] board) {
if (board == null || board.length == 0) return;
int rows = board.length, cols = board[0].length;
Queue<int[]> queue = new LinkedList<>();
// Enqueue all border O's
for (int r = 0; r < rows; r++) {
if (board[r][0] == 'O') { board[r][0] = 'S'; queue.add(new int[]{r, 0}); }
if (board[r][cols-1] == 'O') { board[r][cols-1] = 'S'; queue.add(new int[]{r, cols-1}); }
}
for (int c = 0; c < cols; c++) {
if (board[0][c] == 'O') { board[0][c] = 'S'; queue.add(new int[]{0, c}); }
if (board[rows-1][c] == 'O') { board[rows-1][c] = 'S'; queue.add(new int[]{rows-1, c}); }
}
int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
while (!queue.isEmpty()) {
int[] cell = queue.poll();
for (int[] d : dirs) {
int nr = cell[0]+d[0], nc = cell[1]+d[1];
if (nr >= 0 && nc >= 0 && nr < rows && nc < cols && board[nr][nc] == 'O') {
board[nr][nc] = 'S';
queue.add(new int[]{nr, nc});
}
}
}
// Sweep
for (int r = 0; r < rows; r++)
for (int c = 0; c < cols; c++)
board[r][c] = board[r][c] == 'S' ? 'O' : 'X';
}
public static void main(String[] args) {
char[][] board = {
{'X','X','X','X'},
{'X','O','O','X'},
{'X','X','O','X'},
{'X','O','X','X'}
};
new SurroundedRegionsBFS().solve(board);
for (char[] row : board) System.out.println(new String(row));
}
}
XXXX
XXXX
XXXX
XOXX
What should a senior engineer know?
A senior engineer recognises this as a problem-inversion pattern that appears in many graph problems. The idea of marking the complement and capturing the rest applies to boundary-connected component problems in image processing, game of life variants, and territory control. They also know that using a sentinel in-place saves memory over a separate visited matrix, and that BFS is safer for production-sized boards.
package com.bank.service;
public class SeniorSurroundedNotes {
public static void main(String[] args) {
System.out.println("Senior insights:");
System.out.println(" 1. Problem inversion: mark complement, capture rest.");
System.out.println(" 2. Sentinel saves memory over visited matrix.");
System.out.println(" 3. BFS safer for large boards (no stack overflow).");
System.out.println(" 4. Time: O(rows * cols), Space: O(rows * cols) worst case.");
}
}
Visual Overview
Surrounded Regions: Border DFS + Sweep
Original Board: After Border DFS:
┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐
│ X │ X │ X │ X │ │ X │ X │ X │ X │
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ X │ O │ O │ X │ │ X │ O │ O │ X │ (enclosed, still O)
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ X │ X │ O │ X │ │ X │ X │ O │ X │ (enclosed, still O)
├───┼───┼───┼───┤ ├───┼───┼───┼───┤
│ X │ O │ X │ X │ │ X │ S │ X │ X │ (border-connected, marked S)
└───┴───┴───┴───┘ └───┴───┴───┴───┘
After Sweep:
┌───┬───┬───┬───┐
│ X │ X │ X │ X │
├───┼───┼───┼───┤
│ X │ X │ X │ X │ O -> X (captured)
├───┼───┼───┼───┤
│ X │ X │ X │ X │ O -> X (captured)
├───┼───┼───┼───┤
│ X │ O │ X │ X │ S -> O (restored)
└───┴───┴───┴───┘
Key Takeaway
Surrounded Regions asks you to flip every 'O' that is fully enclosed by 'X' into 'X', while leaving any 'O' connected to the border alone. Detecting enclosure directly is awkward because a single escape path to the border protects an entire region. So the problem is inverted: mark every 'O' reachable from a border 'O' as safe using a sentinel, then sweep the board capturing the complement.
The algorithm seeds a DFS or BFS from every 'O' on the four edges, spreading only through 'O' cells and marking each with a temporary sentinel like 'S'. After this phase, enclosed 'O' cells remain unmarked while safe ones are marked 'S'. The final sweep flips every remaining 'O' to 'X' and restores every 'S' to 'O'. Using the sentinel in-place avoids the need for a separate visited matrix.
The time is O(rows times cols) because the border search and the final sweep each touch every cell a constant number of times. The space is the recursion stack or queue, bounded by the board size. BFS is preferred for production-sized boards to avoid stack overflow.
At the National Bank of India, a jurisdiction grid marked open exposures. An exposure counted as contained only if it was fully enclosed with no path to the border. Rajesh used border-seeded marking to protect every exposure connected to an edge, then flipped the rest to closed, correctly capturing contained exposures while sparing any region with even a single border escape.
Remember one sentence: seed DFS from border 'O' cells to mark safe ones with a sentinel, then sweep to capture every unmarked 'O' and restore the sentinels.
---