Surrounded Regions

Time — O(m*n): each cell visited a constant number of times.
Space — O(m*n): recursion/queue worst case.

Medium

Topics

GraphDFSBFSMatrix

Given an m x n board of 'X' and 'O', capture all regions of 'O' that are fully surrounded by 'X' (flip them to 'X'). Any 'O' connected to the border is safe. Return the resulting board.

Example 1

Input:  board = ["XXXX","XOOX","XXOX","XOXX"]
Output: ["XXXX","XXXX","XXXX","XOXX"]

Constraints

1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Run ⌘' · Submit ⌘⏎