Surrounded Regions
OracleThe problem
You are given a matrix mat of size N x M where each cell contains either** 'O'** or 'X'. Your task is to replace all 'O' cells that are completely surrounded by 'X' with** 'X'**.
Rules:
- An** 'O'** (or a group of connected** 'O'**s) is considered surrounded if it is not connected to any border of the matrix.
- Two** 'O' **cells are considered connected if they are adjacent horizontally or vertically (not diagonally).
- A region of connected** 'O'**s that touches the border (i.e., first row, last row, first column, or last column) is not surrounded and should not be changed.
Input: mat = [ ["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"] ] Explanation:
The 'O' cells at positions (1,1), (1,2), (2,2), and (3,1) are surrounded by 'X' cells in all directions (horizontally and vertically). However, the 'O' region at (3,1) is adjacent to an edge of the board, so it cannot be completely surrounded by 'X' cells. Therefore, it remains unchanged.
Input: mat = [ ["X", "X", "X"], ["X", "O", "X"], ["X", "X", "X"] ] Output: [ ["X", "X", "X"], ["X", "X", "X"], ["X", "X", "X"] ] Explanation: The only 'O' cell at position (1,1) is completely surrounded by 'X' cells in all directions (horizontally and vertically). Hence, it is replaced with 'X' in the output.
Input: mat = [ ["X", "X", "X", "O"], ["X", "X", "X", "X"], ["O", "X", "X", "X"], ["X", "X", "X", "X"] ]
- N == mat.length
- M == mat[i].length
- 1 <= N, M <= 300
- mat[i][j] is 'X' or 'O'.
cpp
class Solution{
public:
vector<vector<char>> fill(vector<vector<char>> mat) {
}
};java
class Solution {
public char[][] fill(char[][] mat) {
}
}python
class Solution:
def fill(self, mat):javascript
class Solution {
fill(mat) {
}
}csharp
public class Solution {
public char[][] Fill(char[][] mat) {
}
}go
func fill(mat [][]string) [][]string {
}Stuck? Show a way to structure it+
- 01Seed DFS/BFS from every border O
- 02Mark reachable cells with a temporary symbol
- 03Scan interior cells and flip unmarked O values
- 04Restore temporary marks
Reference answer
Then expect these follow-ups
How would union-find solve this?
Tests: follow-up reasoning
Why are border-connected cells preserved?
Tests: correctness reasoning
Free to read · better with Enzo
Practice this out loud with Enzo
Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.
Next question