Surrounded regions

Array Depth-First Search Breadth-First Search Union-Find Matrix

44.8% acceptance

Jan 12, 2026

9809

2223

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded: Connect: A cell is connected to adjacent cells horizontally or vertically. Region: To form a region connect every 'O' cell. Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board. To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn solve(board: &mut Vec<Vec<char>>) {
    if board.is_empty() {
      return;
    }
    
    let m = board.len();
    let n = board[0].len();
    
    // Mark border-connected 'O's as 'T'
    for i in 0..m {
      if board[i][0] == 'O' {
        Self::region_dfs(board, i, 0);
      }
      if board[i][n - 1] == 'O' {
        Self::region_dfs(board, i, n - 1);
      }
    }
    
    for j in 0..n {
      if board[0][j] == 'O' {
        Self::region_dfs(board, 0, j);
      }
      if board[m - 1][j] == 'O' {
        Self::region_dfs(board, m - 1, j);
      }
    }
    
    // Flip remaining 'O's to 'X' and restore 'T's to 'O'
    for i in 0..m {
      for j in 0..n {
        if board[i][j] == 'O' {
          board[i][j] = 'X';
        } else if board[i][j] == 'T' {
          board[i][j] = 'O';
        }
      }
    }
  }
  
  fn region_dfs(board: &mut Vec<Vec<char>>, i: usize, j: usize) {
    if i >= board.len() || j >= board[0].len() || board[i][j] != 'O' {
      return;
    }
    
    board[i][j] = 'T';
    
    if i > 0 {
      Self::region_dfs(board, i - 1, j);
    }
    if i < board.len() - 1 {
      Self::region_dfs(board, i + 1, j);
    }
    if j > 0 {
      Self::region_dfs(board, i, j - 1);
    }
    if j < board[0].len() - 1 {
      Self::region_dfs(board, i, j + 1);
    }
  }
}