LeetCode 130 Surrounded Regions - Example and Complexity Analysis

Trace the example board.

Border 'O's: only (3,1) is 'O' on the border (left edge).

DFS from (3,1). Mark as 'S'. No neighbors are 'O'.

Board after marking:

X X X X
X O O X
X X O X
X S X X

Flip remaining 'O's to 'X':

X X X X
X X X X
X X X X
X S X X

Change 'S' back to 'O':

X X X X
X X X X
X X X X
X O X X

Border scan: $O(m + n)$. DFS: $O(m \cdot n)$. Final passes: $O(m \cdot n)$. Total: $O(m \cdot n)$.