← Create New Paste

Surrounded Regions (LeetCode 130): Think From the Border In

5 views
You get an m x n board of 'X' and 'O' characters. Capture every region of 'O' cells that is completely surrounded by 'X' by flipping those cells to 'X'. An 'O' region survives only if at least one of its cells touches the edge of the board. It looks like a plain flood-fill problem, but the trick that makes it easy is to reverse the question. The reversal Checking every region to decide whether it is "surrounded" is awkward: you have to explore the whole region before you know its fate, then go back and flip it. Instead, ask the opposite question: which 'O' cells can never be captured? Exactly the ones connected to a border 'O'. So: 1. Walk the four edges. For every 'O' on an edge, flood-fill from it and mark every reachable 'O' as safe (for example, change it to '#'). 2. Scan the whole board. Any remaining 'O' is surrounded, so flip it to 'X'. Any '#' was safe, so turn it back into 'O'. Each cell is visited a constant number of times, so time is O(m*n). Saying "I will start from the border instead of from each region" early in the interview is the moment the interviewer relaxes. Code (BFS to avoid recursion limits) from collections import deque def solve(board): if not board or not board[0]: return m, n = len(board), len(board[0]) q = deque() for r in range(m): for c in (0, n - 1): if board[r][c] == 'O': board[r][c] = '#'; q.append((r, c)) for c in range(n): for r in (0, m - 1): if board[r][c] == 'O': board[r][c] = '#'; q.append((r, c)) while q: r, c = q.popleft() for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)): nr, nc = r + dr, c + dc if 0 <= nr < m and 0 <= nc < n and board[nr][nc] == 'O': board[nr][nc] = '#'; q.append((nr, nc)) for r in range(m): for c in range(n): if board[r][c] == 'O': board[r][c] = 'X' elif board[r][c] == '#': board[r][c] = 'O' Note that cells are marked when they are pushed, not when they are popped. Marking on pop lets the same cell enter the queue several times, which still gives the right answer but wastes work and is a classic thing interviewers point out. Why BFS over recursive DFS A recursive DFS is shorter, but a 200 x 200 board full of 'O' can recurse 40,000 levels deep and crash Python's default stack. Mention this trade-off out loud; even if you write DFS, showing you know the risk scores points. Union-find is not needed Some candidates reach for a disjoint-set with a virtual "border" node. It works, but it is more code and more chances for bugs. The border-first flood fill is the expected answer. Edge cases to test aloud - Boards with one row or one column: every cell is on the border, nothing flips. - A board of all 'X': nothing to do. - An 'O' region that touches the border only through a diagonal: diagonals do not count, so it gets captured. Related problems The same "start from the boundary" idea solves Number of Enclaves (LeetCode 1020) and Pacific Atlantic Water Flow (LeetCode 417). If you recognise the pattern, you can solve all three with one template. Practising under real pressure Knowing the trick at your desk is different from finding it while someone watches you type. Talk through the reversal before coding, then dry-run a 4 x 4 example. If you want support during the actual interview, Linkjob AI (https://linkjob.ai) gives real-time help during live job interviews and technical interviews, so you can stay on track with your approach and explanation while the clock is running.
Created Nov 18, 2026 00:32 Expires Nov 18, 2027 00:32