Skip to main content

Questions Categories Patterns Progress

CodeTutor - Coding Interview Preparation

Surrounded Regions | CodeTutor

Surrounded Regions

Medium

Arrays Graphs Matrix Traversal DFS (Depth-First Search)BFS (Breadth-First Search)

Problem

You are given an m x n matrix board containing letters 'X' and 'O'. Capture all 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: A 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.

Constraints

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'

Examples

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"]]

The O's in the center form a surrounded region and are captured. The O at the bottom-left edge is not surrounded (it touches the boundary), so it remains unchanged.

Input: board = [["X"]]

Output: [["X"]]

A single X cell has no O's to capture.

Loading...

Loading Python...