MediumNeetCode150Depth-First SearchBreadth-First SearchUnion FindMatrix
Surrounded Regions
Capture surrounded 'O' regions.
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]]
Captured all 'O' except border-connected.
Constraints
- •
m,n <= 200 - •
board[i][j] is 'X' or 'O'
Approaches
Mark border-connected O's.
CodeT: O(m*n) | S: O(m*n)
BFS from edges.
CodeT: O(m*n) | S: O(m*n)
Same approach.
CodeT: O(m*n) | S: O(m*n)
Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| DFS Mark Border Connected | O(m*n) | O(m*n) | Mark border-connected O's. |
| BFS from Borders | O(m*n) | O(m*n) | BFS from edges. |
| BFS Optimized | O(m*n) | O(m*n) | Same approach. |
DFS Mark Border Connected
T: O(m*n)S: O(m*n)
Mark border-connected O's.
BFS from Borders
T: O(m*n)S: O(m*n)
BFS from edges.
BFS Optimized
T: O(m*n)S: O(m*n)
Same approach.
Common Mistakes
Not marking protected cells
Forgetting to restore S->O
Not handling edge cells