Surrounded Regions
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Capture every region of 'O' that is completely surrounded by 'X': flip those O's to X. O's connected to the border are not captured.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1Which O's can never be captured?
- Hint 2Mark those and everything connected to them with a temporary letter, e.g. S.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Islands in a lake with a fence around the edge. A puddle (O) can escape if it connects to the edge, where the water can drain away. So start at every puddle on the edge, mark every connected puddle as "safe", and then everything else that is still a puddle is trapped: fill it with mud (X). Finally turn the safe marks back into puddles.
- The obvious way
For every O region test whether it touches the border: fine, but you would repeat the flood. The border-first approach does one pass.
- The key insight
Flood from every border 'O', changing each reached O to 'S'. Then scan the whole board: remaining 'O' become 'X' (they were trapped), and 'S' become 'O' (they were safe).
- The algorithm
- For every O on the border, flood and mark connected O's as S.
- Scan the board.
- O (still unmarked) -> X.
- S -> O.
Watch it run
Exampleboard rows: XXXX / XOOX / XXOX / XOXX
Border O's: only one, in the bottom row. Mark it S; it has no O neighbours to spread to.
safe: bottom O
Where people slip
- Do not flip O's first: you would also flip the safe ones. Mark the safe ones before changing anything else.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def solve(board):
rows, columns = len(board), len(board[0])
to_visit = []
for row in range(rows):
for column in range(columns):
on_border = row in (0, rows - 1) or column in (0, columns - 1)
if on_border and board[row][column] == "O":
board[row][column] = "S" # safe: it can drain away
to_visit.append((row, column))
while to_visit:
r, c = to_visit.pop()
for next_row, next_column in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= next_row < rows and 0 <= next_column < columns and board[next_row][next_column] == "O":
board[next_row][next_column] = "S"
to_visit.append((next_row, next_column))
for row in range(rows):
for column in range(columns):
if board[row][column] == "O":
board[row][column] = "X" # trapped: fill with mud
elif board[row][column] == "S":
board[row][column] = "O" # safe: back to a puddleNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.