/130. Surrounded Regions

130. Surrounded Regions

Medium
Arrays44.9% acceptance

Given a 2D matrix grid of size m x n containing only characters X and O, modify the grid in-place so that all O regions that are fully surrounded by X are replaced with X. An O region is defined as a group of horizontally or vertically connected O cells. A region is considered surrounded if none of its cells touch the border of the grid. The function should update the input grid in-place and does not return anything.

Example 1

Input: [[X,O,X,X],[O,O,X,O],[X,X,O,X],[O,X,X,O]]

Output: [[X,O,X,X],[O,O,X,O],[X,X,O,X],[O,X,X,O]]

Explanation: No surrounded region exists, so no change.

Example 2

Input: [[O,O,O],[O,X,O],[O,O,O]]

Output: [[O,O,O],[O,X,O],[O,O,O]]

Explanation: The central X is surrounded by O, but O regions touch the border, so no change.

Example 3

Input: [[X,X,X],[X,O,X],[X,X,X]]

Output: [[X,X,X],[X,X,X],[X,X,X]]

Explanation: The single O is surrounded and converted to X.

Constraints

  • 1 <= len(grid) <= 200
  • 1 <= len(grid[0]) <= 200
  • grid[i][j] in {X, O} for all valid i, j
Python (current runtime)

Case 1

Input: [['X','O','X'],['O','O','X'],['X','X','O']]

Expected: [['X','O','X'],['O','O','X'],['X','X','O']]

Case 2

Input: [['X','X','O','X'],['O','O','X','O'],['X','O','O','X'],['X','X','X','O']]

Expected: [['X','X','O','X'],['O','O','X','O'],['X','O','O','X'],['X','X','X','O']]

Case 3

Input: [['X','X','X','X'],['X','O','O','X'],['X','O','O','X'],['X','X','X','X']]

Expected: [['X','X','X','X'],['X','X','X','X'],['X','X','X','X'],['X','X','X','X']]

Case 4

Input: [['O','X','O'],['X','O','X'],['O','X','O']]

Expected: [['O','X','O'],['X','O','X'],['O','X','O']]

Case 5

Input: [['X','O'],['O','X']]

Expected: [['X','O'],['O','X']]