Surrounded Regions in Matrix using Graph Traversal

Given a 2D matrix of size N x M filled with characters 'O' and 'X', the goal is to replace all 'O' cells that are completely surrounded by 'X' on all four sides (up, down, left, right).

'O's that are on the border or connected to a border 'O' should not be changed. Only 'O's that are fully enclosed by 'X' must be replaced.

Understanding the Problem

We are given a 2D matrix filled with characters 'X' and 'O'. The goal is to identify and convert all 'O' regions that are completely surrounded by 'X' into 'X's. An 'O' region is defined as a group of connected 'O's (connected horizontally or vertically).

However, if any 'O' in a region is on the border (top row, bottom row, leftmost column, or rightmost column), or is connected to a border 'O', that region is considered safe and should not be converted.

Step-by-Step Solution with Example

Step 1: Identify and understand the input

Let’s take this input matrix:

X X X X
X O O X
X X O X
X O X X

We need to determine which 'O's are surrounded and which are connected to the border.

Step 2: Mark the border-connected 'O's

Start by checking the border cells. If an 'O' is found on the border, perform a BFS/DFS to mark it and all connected 'O's as safe (we can use a temporary marker like '#').

In our example, matrix[3][1] is an 'O' on the border. It is safe. We mark it as '#'. But this 'O' is not connected to any other 'O', so only this cell gets marked.

Step 3: Traverse the matrix to convert unsafe 'O's

Now scan the entire matrix:

• If a cell is 'O', it means it is not connected to any border 'O'. It is unsafe and must be converted to 'X'.
• If a cell is '#', it was marked safe earlier and should be converted back to 'O'.

After this step, our matrix becomes:

X X X X
X X X X
X X X X
X O X X

Step 4: Finalize the matrix

Replace all '#' back to 'O'. Now we have the final matrix with all truly surrounded regions converted and border-connected regions preserved.

Edge Cases

• Empty matrix: No operation needed.
• All 'X's: No changes required.
• All 'O's on border: No 'O' should be changed.
• Matrix with only 1 row or 1 column: All 'O's are border cells and remain unchanged.

Finally

This problem teaches us how to use graph traversal techniques like DFS or BFS to identify connected components, especially under constraints like "not surrounded." Marking safe regions with a temporary symbol is a common trick in matrix-based problems. Always process border-related constraints first and then use a second pass to finalize the result.

1. Loop through the border rows and columns of the matrix.
2. If an 'O' is found on the border, start a DFS/BFS from there to mark all connected 'O's as '#'.
3. After marking, traverse the entire matrix:
1. If a cell is 'O', change it to 'X'.
2. If a cell is '#', revert it to 'O'.

#include <stdio.h>
#define ROWS 4
#define COLS 4

void dfs(char board[ROWS][COLS], int r, int c) {
    if (r < 0 || c < 0 || r >= ROWS || c >= COLS || 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);
}

void solve(char board[ROWS][COLS]) {
    for (int i = 0; i < ROWS; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][COLS - 1] == 'O') dfs(board, i, COLS - 1);
    }
    for (int j = 0; j < COLS; j++) {
        if (board[0][j] == 'O') dfs(board, 0, j);
        if (board[ROWS - 1][j] == 'O') dfs(board, ROWS - 1, j);
    }
    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] == '#') board[i][j] = 'O';
        }
    }
}

int main() {
    char board[ROWS][COLS] = {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };

    solve(board);

    printf("Updated Board:\n");
    for (int i = 0; i < ROWS; i++) {
        for (int j = 0; j < COLS; j++) {
            printf("%c ", board[i][j]);
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void dfs(vector<vector<char>>& board, int r, int c) {
    int rows = board.size(), cols = board[0].size();
    if (r < 0 || c < 0 || r >= rows || c >= cols || 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);
}

void solve(vector<vector<char>>& board) {
    int rows = board.size(), cols = board[0].size();
    for (int i = 0; i < rows; i++) {
        if (board[i][0] == 'O') dfs(board, i, 0);
        if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1);
    }
    for (int j = 0; j < cols; j++) {
        if (board[0][j] == 'O') dfs(board, 0, j);
        if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j);
    }
    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] == '#') board[i][j] = 'O';
        }
    }
}

int main() {
    vector<vector<char>> board = {
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'}
    };

    solve(board);

    cout << "Updated Board:\n";
    for (auto& row : board) {
        for (char c : row) cout << c << ' ';
        cout << '\n';
    }
    return 0;
}

def dfs(board, r, c):
    if r < 0 or c < 0 or r >= len(board) or c >= len(board[0]) or 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)

def solve(board):
    if not board: return
    rows, cols = len(board), len(board[0])
    for i in range(rows):
        if board[i][0] == 'O': dfs(board, i, 0)
        if board[i][cols-1] == 'O': dfs(board, i, cols-1)
    for j in range(cols):
        if board[0][j] == 'O': dfs(board, 0, j)
        if board[rows-1][j] == 'O': dfs(board, rows-1, j)
    for i in range(rows):
        for j in range(cols):
            if board[i][j] == 'O': board[i][j] = 'X'
            if board[i][j] == '#': board[i][j] = 'O'

board = [
    ['X','X','X','X'],
    ['X','O','O','X'],
    ['X','X','O','X'],
    ['X','O','X','X']
]

solve(board)
print("Updated Board:")
for row in board:
    print(' '.join(row))

public class SurroundedRegions {
    public static void main(String[] args) {
        char[][] board = {
            {'X','X','X','X'},
            {'X','O','O','X'},
            {'X','X','O','X'},
            {'X','O','X','X'}
        };
        solve(board);
        System.out.println("Updated Board:");
        for (char[] row : board) {
            for (char c : row) System.out.print(c + " ");
            System.out.println();
        }
    }

    static void dfs(char[][] board, int r, int c) {
        int rows = board.length, cols = board[0].length;
        if (r < 0 || c < 0 || r >= rows || c >= cols || 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);
    }

    static void solve(char[][] board) {
        int rows = board.length, cols = board[0].length;
        for (int i = 0; i < rows; i++) {
            if (board[i][0] == 'O') dfs(board, i, 0);
            if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1);
        }
        for (int j = 0; j < cols; j++) {
            if (board[0][j] == 'O') dfs(board, 0, j);
            if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j);
        }
        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] == '#') board[i][j] = 'O';
            }
        }
    }
}

function solve(board) {
  const rows = board.length;
  if (rows === 0) return;
  const cols = board[0].length;

  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== 'O') return;
    board[r][c] = '#';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let i = 0; i < rows; i++) {
    if (board[i][0] === 'O') dfs(i, 0);
    if (board[i][cols - 1] === 'O') dfs(i, cols - 1);
  }

  for (let j = 0; j < cols; j++) {
    if (board[0][j] === 'O') dfs(0, j);
    if (board[rows - 1][j] === 'O') dfs(rows - 1, j);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === '#') board[i][j] = 'O';
    }
  }
  return board;
}

const board = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"]
];

console.log("Updated Board:", solve(board));

package main

import (
    "fmt"
)

func dfs(board [][]byte, r, c int) {
    rows, cols := len(board), len(board[0])
    if r < 0 || c < 0 || r >= rows || c >= cols || 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)
}

func solve(board [][]byte) {
    rows, cols := len(board), len(board[0])
    for i := 0; i < rows; i++ {
        if board[i][0] == 'O' {
            dfs(board, i, 0)
        }
        if board[i][cols-1] == 'O' {
            dfs(board, i, cols-1)
        }
    }
    for j := 0; j < cols; j++ {
        if board[0][j] == 'O' {
            dfs(board, 0, j)
        }
        if board[rows-1][j] == 'O' {
            dfs(board, rows-1, j)
        }
    }
    for i := 0; i < rows; i++ {
        for j := 0; j < cols; j++ {
            if board[i][j] == 'O' {
                board[i][j] = 'X'
            } else if board[i][j] == '#' {
                board[i][j] = 'O'
            }
        }
    }
}

func main() {
    board := [][]byte{
        {'X','X','X','X'},
        {'X','O','O','X'},
        {'X','X','O','X'},
        {'X','O','X','X'},
    }
    solve(board)
    fmt.Println("Updated Board:")
    for _, row := range board {
        fmt.Println(string(row))
    }
}

fn dfs(board: &mut Vec<Vec<char>>, r: isize, c: isize) {
    let rows = board.len() as isize;
    let cols = board[0].len() as isize;
    if r < 0 || c < 0 || r >= rows || c >= cols || board[r as usize][c as usize] != 'O' {
        return;
    }
    board[r as usize][c as usize] = '#';
    dfs(board, r + 1, c);
    dfs(board, r - 1, c);
    dfs(board, r, c + 1);
    dfs(board, r, c - 1);
}

fn solve(board: &mut Vec<Vec<char>>) {
    let rows = board.len();
    let cols = board[0].len();

    for i in 0..rows {
        if board[i][0] == 'O' {
            dfs(board, i as isize, 0);
        }
        if board[i][cols - 1] == 'O' {
            dfs(board, i as isize, (cols - 1) as isize);
        }
    }

    for j in 0..cols {
        if board[0][j] == 'O' {
            dfs(board, 0, j as isize);
        }
        if board[rows - 1][j] == 'O' {
            dfs(board, (rows - 1) as isize, j as isize);
        }
    }

    for i in 0..rows {
        for j in 0..cols {
            if board[i][j] == 'O' {
                board[i][j] = 'X';
            } else if board[i][j] == '#' {
                board[i][j] = 'O';
            }
        }
    }
}

fn main() {
    let mut board = vec![
        vec!['X', 'X', 'X', 'X'],
        vec!['X', 'O', 'O', 'X'],
        vec!['X', 'X', 'O', 'X'],
        vec!['X', 'O', 'X', 'X'],
    ];

    solve(&mut board);

    println!("Updated Board:");
    for row in &board {
        println!("{:?}", row);
    }
}

fun dfs(board: Array<CharArray>, r: Int, c: Int) {
    val rows = board.size
    val cols = board[0].size
    if (r < 0 || c < 0 || r >= rows || c >= cols || 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)
}

fun solve(board: Array<CharArray>) {
    val rows = board.size
    val cols = board[0].size
    for (i in 0 until rows) {
        if (board[i][0] == 'O') dfs(board, i, 0)
        if (board[i][cols - 1] == 'O') dfs(board, i, cols - 1)
    }
    for (j in 0 until cols) {
        if (board[0][j] == 'O') dfs(board, 0, j)
        if (board[rows - 1][j] == 'O') dfs(board, rows - 1, j)
    }
    for (i in 0 until rows) {
        for (j in 0 until cols) {
            if (board[i][j] == 'O') board[i][j] = 'X'
            if (board[i][j] == '#') board[i][j] = 'O'
        }
    }
}

fun main() {
    val board = arrayOf(
        charArrayOf('X','X','X','X'),
        charArrayOf('X','O','O','X'),
        charArrayOf('X','X','O','X'),
        charArrayOf('X','O','X','X')
    )
    solve(board)
    println("Updated Board:")
    for (row in board) {
        println(row.joinToString(" "))
    }
}

func dfs(_ board: inout [[Character]], _ r: Int, _ c: Int) {
    let rows = board.count
    let cols = board[0].count
    if r < 0 || c < 0 || r >= rows || c >= cols || 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)
}

func solve(_ board: inout [[Character]]) {
    let rows = board.count
    let cols = board[0].count
    for i in 0..<rows {
        if board[i][0] == "O" { dfs(&board, i, 0) }
        if board[i][cols - 1] == "O" { dfs(&board, i, cols - 1) }
    }
    for j in 0..<cols {
        if board[0][j] == "O" { dfs(&board, 0, j) }
        if board[rows - 1][j] == "O" { dfs(&board, rows - 1, j) }
    }
    for i in 0..<rows {
        for j in 0..<cols {
            if board[i][j] == "O" {
                board[i][j] = "X"
            } else if board[i][j] == "#" {
                board[i][j] = "O"
            }
        }
    }
}

var board: [[Character]] = [
    ["X","X","X","X"],
    ["X","O","O","X"],
    ["X","X","O","X"],
    ["X","O","X","X"]
]

solve(&board)
print("Updated Board:")
for row in board {
    print(row.map { String($0) }.joined(separator: " "))
}

function solve(board: string[][]): string[][] {
  const rows = board.length;
  const cols = board[0].length;

  function dfs(r: number, c: number): void {
    if (r < 0 || c < 0 || r >= rows || c >= cols || board[r][c] !== 'O') return;
    board[r][c] = '#';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let i = 0; i < rows; i++) {
    if (board[i][0] === 'O') dfs(i, 0);
    if (board[i][cols - 1] === 'O') dfs(i, cols - 1);
  }

  for (let j = 0; j < cols; j++) {
    if (board[0][j] === 'O') dfs(0, j);
    if (board[rows - 1][j] === 'O') dfs(rows - 1, j);
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (board[i][j] === 'O') board[i][j] = 'X';
      if (board[i][j] === '#') board[i][j] = 'O';
    }
  }

  return board;
}

const board: string[][] = [
  ["X", "X", "X", "X"],
  ["X", "O", "O", "X"],
  ["X", "X", "O", "X"],
  ["X", "O", "X", "X"]
];

console.log("Updated Board:", solve(board));

Time complexity

Space complexity

O(m × n)

In the worst case, a DFS/BFS queue or recursion stack can hold all cells in the matrix when marking connected regions.