Drain the Landlocked Ponds

Medium

A map is given as an m × n grid grid, where 'X' is land and 'O' is water. Water cells that are horizontally or vertically adjacent belong to the same pond. A pond with no cell on the edge of the map is landlocked: its water has nowhere to go. Drain every landlocked pond by turning its cells into 'X'. Ponds that touch the edge stay as they are. Return the map after draining.

Example 1

grid=[['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X']] → [['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'X', 'X', 'X'], ['X', 'X', 'O', 'X']]

The two-cell pond in the second column is enclosed by land on all sides, so it is drained. The cell on the right of the second row and the one at the bottom touch the edge of the map and stay water.

Example 2

grid=[['O', 'O', 'O'], ['O', 'X', 'O'], ['O', 'O', 'O']] → [['O', 'O', 'O'], ['O', 'X', 'O'], ['O', 'O', 'O']]

All the water touches the edge, so nothing changes.

Example 3

grid=[['X', 'X', 'X'], ['X', 'O', 'X'], ['X', 'X', 'X']] → [['X', 'X', 'X'], ['X', 'X', 'X'], ['X', 'X', 'X']]

The single water cell in the middle is surrounded by land and turns into land.

Constraints

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

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

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

Similar problems

Land Regions on a Map Medium Largest Forest Patch Medium A Board Cut by Slashes Medium Landlocked Land Cells Medium Route With the Highest Bottleneck Medium

Input

grid=[['X', 'X', 'X', 'X'], ['X', 'O', 'X', 'O'], ['X', 'O', 'X', 'X'], ['X', 'X', 'O', 'X']]

Expected

[['X', 'X', 'X', 'X'], ['X', 'X', 'X', 'O'], ['X', 'X', 'X', 'X'], ['X', 'X', 'O', 'X']]

Run checks the first 3 tests in your browser. Submit checks all 36 tests on the server, hidden ones included.