Surrounded Regions - Graph-Based Matrix Problem - Visualization

Graphs

Contents

VisualizationProblemExamplesSolutionAlgorithmCodeTimeSpace

Visualization Player

Problem Statement❯

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.

Examples❯

Input Matrix Output Matrix Description
[["X", "X", "X", "X"], ["X", "O", "O", "X"], ["X", "X", "O", "X"], ["X", "O", "X", "X"]]
[["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "X", "X", "X"], ["X", "O", "X", "X"]]
'O's at (1,1), (1,2), (2,2) are surrounded, so flipped
[["O", "O"], ["O", "O"]]
[["O", "O"], ["O", "O"]]
All 'O's are on border or connected to border, so remain unchanged
[["X"]]
[["X"]]
Single cell matrix, no changes
[["O"]]
[["O"]]
Single 'O' on border, not flipped
[] [] Empty matrix, no operation
[["X", "X", "X", "X"], ["X", "O", "O", "X"], ["O", "X", "X", "X"], ["X", "O", "X", "O"], ["O", "O", "X", "X"]]
[["X", "X", "X", "X"], ["X", "X", "X", "X"], ["O", "X", "X", "X"], ["X", "O", "X", "O"], ["O", "O", "X", "X"]]
Internal 'O's surrounded and flipped, border-connected 'O's remain

Solution❯

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.

Algorithm Steps❯

  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'.

Code

C
C++
Python
Java
JS
Go
Rust
Kotlin
Swift
TS
#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;
}

Time Complexity❯

CaseTime ComplexityExplanation
Best CaseO(m × n)Even if there are no 'O's in the matrix, the algorithm must check every border element and traverse the matrix once.
Average CaseO(m × n)Each cell is visited once during border traversal and once during the final transformation, resulting in linear complexity based on the number of cells.
Worst CaseO(m × n)If the entire matrix is filled with 'O's, DFS/BFS could touch each element multiple times, but the total work remains bounded by O(m × n).

Space Complexity❯

O(m × n)

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


Comments

💬 Please keep your comment relevant and respectful. Avoid spamming, offensive language, or posting promotional/backlink content.
All comments are subject to moderation before being published.

Loading comments...