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
Hiring now
Software engineer roles are open right now
landed applies to roles like these for you, on each company’s own site, with answers written for the role.
Senior Software Engineer -.NET
Tyler Technologies · Annapolis, Maryland
Software Development Engineer II
SaaS Labs · Bengaluru, Karnataka, India
Advanced Software Engineer - Product Architect (Legal, Safety, and Risk)
Metropolitan Transportation Authority · New York, NY
Next question