my dsa gallery
Graph / MatrixBoundary DFS / Flood Fill
Open ProblemEdit

Surrounded Regions

Problem link: https://leetcode.com/problems/surrounded-regions/

Problem Statement

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region. An 'O' is not captured if it is on the edge or connected to an 'O' on the edge.

Input

An m x n board of characters ('X' and 'O').

Output

Void. The board must be modified in-place.

Example

Input: board = [ ["X","X","X","X"], ["X","O","O","X"], ["X","X","O","X"], ["X","O","X","X"] ]

Output: [ ["X","X","X","X"], ["X","X","X","X"], ["X","X","X","X"], ["X","O","X","X"] ]

Explanation

The 'O' at (3,1) is on the boundary, so it stays 'O'. All other 'O's are internal and surrounded by 'X's, so they are flipped to 'X'.

Brute Force

Intuition

For every 'O' encountered, run a DFS to check if it can reach the boundary. If the traversal finishes without touching an edge, mark that whole region for flipping.

Approach

  1. Iterate through every cell $(i, j)$.
  2. If board[i][j] == 'O', start a DFS/BFS.
  3. Track if any cell in this cluster is on the boundary.
  4. If not, re-traverse the cluster to flip to 'X'.
Time: O((M * N)^2)Space: O(M * N)

Optimal Solution

Intuition

Reverse the thinking: Identify which 'O's are NOT surrounded. An 'O' is safe if it is on the boundary or connected to a boundary 'O'.

Approach

  1. Boundary Scan: Loop through the first/last rows and columns.
  2. Marking: For every boundary 'O', trigger a DFS to mark it and its connected neighbors as '#'.
  3. Transformation: Traverse the entire grid:
    • If 'O' -> Change to 'X' (it was surrounded).
    • If '#' -> Change to 'O' (it was safe).
Step 1 of 1- Boundary Mark
Start DFS from (3,1), mark as '#'
Loading...
Use arrow keys to navigate

Code (Java)

class Solution {
    public void solve(char[][] board) {
        if (board == null || board.length == 0) return;
        int m = board.length, n = board[0].length;

        for (int i = 0; i < m; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][n - 1] == 'O') dfs(board, i, n - 1);
        }
        for (int j = 0; j < n; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (board[i][j] == 'O') board[i][j] = 'X';
                else if (board[i][j] == '#') board[i][j] = 'O';
            }
        }
    }

    private void dfs(char[][] board, int r, int c) {
        if (r < 0 || r >= board.length || c < 0 || c >= board[0].length || board[r][c] != 'O') return;
        board[r][c] = '#';
        dfs(board, r + 1, c);
        dfs(board, r - 1, c);
        dfs(board, r, c + 1);
        dfs(board, r, c - 1);
    }
}
Time: O(M * N)Space: O(M * N)

Complexity Analysis

Every cell is processed a constant number of times. Space is $O(M \cdot N)$ for the recursion stack in the worst case where many 'O's are connected.

Quick Revision (Brute Force)

  • DFS from every internal 'O' to see if it reaches the edge.
  • Redundant and slow: $O((M \cdot N)^2)$

Quick Revision (Optimal)

  • Boundary DFS Strategy.
  • Identify 'Safe' O's first starting from edges.
  • Anything not marked Safe is surrounded.
  • O(M*N) time complexity.

Study Photos

Upload screenshots/notes for this specific problem.

Drag & drop or click to select
Drop an image anywhere in this box to upload.
No photos uploaded till now.

Comments

Stored in D1. Login required.
  • using BFS : class Solution { public void solve(char[][] board) { Queue<int[]> q = new LinkedList<>(); int m = board.length; int n = board[0].length; for(int i=0;i<m;i++){ if(board[i][0] == 'O'){ board[i][0] = '#'; q.offer(new int[]{i,0}); } if(board[i][n-1] == 'O'){ board[i][n-1] = '#'; q.offer(new int[]{i,n-1}); } } for(int j=0;j<n;j++){ if(board[0][j] == 'O'){ board[0][j] = '#'; q.offer(new int[]{0,j}); } if(board[m-1][j] == 'O'){ board[m-1][j] = '#'; q.offer(new int[]{m-1,j}); } } int[][] dir = {{0,-1},{0,1},{1,0},{-1,0}}; while(!q.isEmpty()){ int[] current = q.poll(); int row = current[0]; int col = current[1]; for(int[] d : dir){ int newRow = d[0] + row; int newCol = d[1] + col; if(newRow >= 0 && newRow < m && newCol >=0 && newCol < n && board[newRow][newCol] == 'O'){ //System.out.println("nR : "+ newRow + " rC : "+ newCol + " r: " + row + " c: " + col); q.offer(new int[]{newRow,newCol}); board[newRow][newCol] = '#'; } } } for(int i=0;i<m;i++){ for(int j=0;j<n;j++){ if(board[i][j] == '#'){ board[i][j] = 'O'; }else{ board[i][j] = 'X'; } } } } }
    2026-04-18T19:36:26.398Z