Lesson 147 of 250
130. Surrounded Regions
NeetCode: Surrounded Regions · LeetCode: 130. Surrounded Regions · Difficulty: Medium
Given an m x n board of 'X' and 'O', capture every region of 'O' cells that is completely surrounded by 'X' (4-directionally connected regions). Captured cells become 'X'. A region that touches the border of the board is not surrounded and stays. As in LeetCode, the method returns nothing and edits the char[][] board in place.
Example
board: XXXX Output: XXXX
XOOX XXXX
XXOX XXXX
XOXX XOXXThe three connected Os in the middle are enclosed, so they flip. The O in the last row is on the border, so it stays.
The examples build a board from strings with a helper parse (String.toCharArray() per row) and print it with a helper show that joins the rows with /.
Brute force: check every O for an escape route
For each 'O' cell, flood fill through 'O' cells and see whether the fill ever reaches a border cell. If it does not, that cell is flipped. All decisions are made against the original board and the flips are applied afterwards.
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
private boolean escapes(char[][] board, int sr, int sc) {
int m = board.length;
int n = board[0].length;
boolean[][] visited = new boolean[m][n];
visited[sr][sc] = true;
Deque<int[]> stack = new ArrayDeque<>();
stack.push(new int[]{sr, sc});
while (!stack.isEmpty()) {
int[] cell = stack.pop();
int r = cell[0];
int c = cell[1];
if (r == 0 || c == 0 || r == m - 1 || c == n - 1) {
return true;
}
for (int[] d : DIRS) {
int nr = r + d[0];
int nc = c + d[1];
if (board[nr][nc] == 'O' && !visited[nr][nc]) {
visited[nr][nc] = true;
stack.push(new int[]{nr, nc});
}
}
}
return false;
}
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0) {
return;
}
List<int[]> toFlip = new ArrayList<>();
for (int r = 0; r < board.length; r++) {
for (int c = 0; c < board[0].length; c++) {
if (board[r][c] == 'O' && !escapes(board, r, c)) {
toFlip.add(new int[]{r, c});
}
}
}
for (int[] cell : toFlip) {
board[cell[0]][cell[1]] = 'X';
}
}
}
public class Main {
static char[][] parse(String... rows) {
char[][] board = new char[rows.length][];
for (int i = 0; i < rows.length; i++) {
board[i] = rows[i].toCharArray();
}
return board;
}
static String show(char[][] board) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < board.length; i++) {
if (i > 0) {
sb.append('/');
}
sb.append(board[i]);
}
return sb.toString();
}
public static void main(String[] args) {
Solution s = new Solution();
char[][] a = parse("XXXX", "XOOX", "XXOX", "XOXX");
s.solve(a);
System.out.println(show(a));
char[][] b = parse("O");
s.solve(b);
System.out.println(show(b));
char[][] c = parse("XXX", "XOX", "XXX");
s.solve(c);
System.out.println(show(c));
}
}XXXX/XXXX/XXXX/XOXX
O
XXX/XXX/XXXNo bounds check is needed for the neighbors: the loop returns as soon as it reaches a border cell, so every cell it expands from is interior and has four neighbors. Without that early return, Java would throw ArrayIndexOutOfBoundsException. Time: O((m * n)^2) worst case, since each 'O' may trigger a full fill. Space: O(m * n).
Optimal: mark what is safe from the border inward
The only 'O' cells that survive are those connected to a border 'O'. Start a flood fill from every border 'O' and mark everything it reaches as 'S' (safe). Every remaining 'O' is then enclosed. A final pass turns 'S' back into 'O' and every other cell into 'X'.
import java.util.ArrayDeque;
import java.util.Deque;
class Solution {
private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public void solve(char[][] board) {
if (board.length == 0 || board[0].length == 0) {
return;
}
int m = board.length;
int n = board[0].length;
Deque<int[]> stack = new ArrayDeque<>();
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
boolean onBorder = r == 0 || c == 0 || r == m - 1 || c == n - 1;
if (onBorder && board[r][c] == 'O') {
board[r][c] = 'S';
stack.push(new int[]{r, c});
}
}
}
while (!stack.isEmpty()) {
int[] cell = stack.pop();
for (int[] d : DIRS) {
int nr = cell[0] + d[0];
int nc = cell[1] + d[1];
if (nr < 0 || nc < 0 || nr >= m || nc >= n) {
continue;
}
if (board[nr][nc] == 'O') {
board[nr][nc] = 'S';
stack.push(new int[]{nr, nc});
}
}
}
for (int r = 0; r < m; r++) {
for (int c = 0; c < n; c++) {
board[r][c] = board[r][c] == 'S' ? 'O' : 'X';
}
}
}
}
public class Main {
static char[][] parse(String... rows) {
char[][] board = new char[rows.length][];
for (int i = 0; i < rows.length; i++) {
board[i] = rows[i].toCharArray();
}
return board;
}
static String show(char[][] board) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < board.length; i++) {
if (i > 0) {
sb.append('/');
}
sb.append(board[i]);
}
return sb.toString();
}
public static void main(String[] args) {
Solution s = new Solution();
char[][] a = parse("XXXX", "XOOX", "XXOX", "XOXX");
s.solve(a);
System.out.println(show(a));
char[][] b = parse("O");
s.solve(b);
System.out.println(show(b));
char[][] c = parse("XXX", "XOX", "XXX");
s.solve(c);
System.out.println(show(c));
}
}XXXX/XXXX/XXXX/XOXX
O
XXX/XXX/XXXIn the final rewrite 'S' becomes 'O', and both leftover 'O' and existing 'X' become 'X'. Time: O(m * n). Space: O(m * n) worst case for the stack.