Solving Surrounded Regions in JavaScript: Step-by-Step Guide

Introduction to Surrounded Regions

The "Surrounded Regions" problem is a classic graph traversal challenge frequently encountered in coding interviews and competitive programming. Given a 2D board containing the characters 'X' and 'O', the goal is to capture all regions of 'O's that are completely surrounded by 'X's — that is, flip them to 'X'. Any 'O' that is connected to the border of the board, directly or indirectly, is considered not surrounded and must remain unchanged.

This problem tests your understanding of depth-first search (DFS), breadth-first search (BFS), and the union-find data structure. It also reinforces the importance of thinking about edge cases and boundary conditions when working with matrices.

Why It Matters

Understanding how to solve the Surrounded Regions problem is valuable for several reasons:

• Graph traversal mastery: It forces you to apply DFS or BFS on a 2D grid, a skill that transfers to many other problems like number of islands, word search, and flood fill.
• Interview relevance: It is a popular LeetCode problem (LC 130) and appears frequently in technical interviews at major tech companies.
• Real-world applications: Similar algorithms are used in image processing (flood fill tools), game development (territory capture games like Go), and geographic information systems.
• Algorithmic thinking: The "reverse thinking" approach — marking what should NOT be captured instead of what should — is a powerful problem-solving technique.

Understanding the Problem

Let's break down the problem with a concrete example. Consider the following board:

[
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
]

After solving, the board should become:

[
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'X', 'X']
]

Notice that the 'O' at position (3, 1) remains unchanged because it is on the border. All other 'O's are fully surrounded by 'X's and get flipped.

Key Observations

• Any 'O' on the border can never be captured.
• Any 'O' connected (4-directionally) to a border 'O' also cannot be captured.
• Only 'O's that form a closed region entirely surrounded by 'X's should be flipped.

The Strategy: Reverse Thinking

Instead of trying to find surrounded regions directly (which is tricky because you would need to verify that a region has no path to the border), we flip the problem on its head:

1. Find all 'O's on the border of the board.
2. Use DFS or BFS to mark every 'O' connected to those border 'O's with a temporary marker, such as 'T'.
3. Iterate through the entire board:
   • Flip every remaining 'O' to 'X' (these are the surrounded ones).
   • Flip every 'T' back to 'O' (these are the safe ones).

This approach is clean, efficient, and easy to reason about.

Step-by-Step Implementation

Step 1: Setting Up the Function Signature

We will modify the board in place, which is the typical requirement for this problem.

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
function solve(board) {
  if (!board || board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;

  // Step 2 and Step 3 will go here
}

Step 2: Defining the DFS Helper Function

We need a helper function that performs DFS from a given cell, marking all connected 'O's as 'T'.

function dfs(r, c) {
  // Check bounds and whether the cell is an 'O'
  if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') {
    return;
  }

  // Mark as visited with a temporary marker
  board[r][c] = 'T';

  // Explore all four directions
  dfs(r + 1, c);
  dfs(r - 1, c);
  dfs(r, c + 1);
  dfs(r, c - 1);
}

Step 3: Marking Border-Connected Regions

We iterate over the border rows and columns, calling DFS on any 'O' we find.

// Top and bottom rows
for (let c = 0; c < cols; c++) {
  if (board[0][c] === 'O') dfs(0, c);
  if (board[rows - 1][c] === 'O') dfs(rows - 1, c);
}

// Left and right columns
for (let r = 0; r < rows; r++) {
  if (board[r][0] === 'O') dfs(r, 0);
  if (board[r][cols - 1] === 'O') dfs(r, cols - 1);
}

Step 4: Final Board Update

Now we traverse the entire board one more time to apply the final transformations.

for (let r = 0; r < rows; r++) {
  for (let c = 0; c < cols; c++) {
    if (board[r][c] === 'O') {
      board[r][c] = 'X'; // Surrounded, flip it
    } else if (board[r][c] === 'T') {
      board[r][c] = 'O'; // Border-connected, restore it
    }
  }
}

Complete Solution

Here is the full, working implementation putting all the pieces together:

/**
 * Solves the Surrounded Regions problem in place.
 * @param {character[][]} board
 * @return {void}
 */
function solve(board) {
  if (!board || board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;

  // DFS helper to mark border-connected 'O's
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') {
      return;
    }
    board[r][c] = 'T';
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  // Mark all 'O's connected to the border
  for (let c = 0; c < cols; c++) {
    if (board[0][c] === 'O') dfs(0, c);
    if (board[rows - 1][c] === 'O') dfs(rows - 1, c);
  }
  for (let r = 0; r < rows; r++) {
    if (board[r][0] === 'O') dfs(r, 0);
    if (board[r][cols - 1] === 'O') dfs(r, cols - 1);
  }

  // Flip remaining 'O' to 'X' and restore 'T' to 'O'
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') {
        board[r][c] = 'X';
      } else if (board[r][c] === 'T') {
        board[r][c] = 'O';
      }
    }
  }
}

// Example usage
const board = [
  ['X', 'X', 'X', 'X'],
  ['X', 'O', 'O', 'X'],
  ['X', 'X', 'O', 'X'],
  ['X', 'O', 'X', 'X']
];

solve(board);
console.log(board);
// Output:
// [
//   ['X', 'X', 'X', 'X'],
//   ['X', 'X', 'X', 'X'],
//   ['X', 'X', 'X', 'X'],
//   ['X', 'O', 'X', 'X']
// ]

Alternative Approach: BFS

If you are concerned about stack overflow with deep recursion on very large boards, you can use an iterative BFS approach instead. Here is how that looks:

function solveBFS(board) {
  if (!board || board.length === 0) return;

  const rows = board.length;
  const cols = board[0].length;
  const queue = [];

  // Collect all border 'O's
  for (let c = 0; c < cols; c++) {
    if (board[0][c] === 'O') queue.push([0, c]);
    if (board[rows - 1][c] === 'O') queue.push([rows - 1, c]);
  }
  for (let r = 0; r < rows; r++) {
    if (board[r][0] === 'O') queue.push([r, 0]);
    if (board[r][cols - 1] === 'O') queue.push([r, cols - 1]);
  }

  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  // BFS to mark all border-connected 'O's
  while (queue.length > 0) {
    const [r, c] = queue.shift();
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== 'O') {
      continue;
    }
    board[r][c] = 'T';
    for (const [dr, dc] of directions) {
      queue.push([r + dr, c + dc]);
    }
  }

  // Final pass
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (board[r][c] === 'O') board[r][c] = 'X';
      else if (board[r][c] === 'T') board[r][c] = 'O';
    }
  }
}

Note that using queue.shift() has O(n) complexity per operation. For better performance on large inputs, consider using a deque or an index pointer instead.

Complexity Analysis

• Time Complexity: O(m × n), where m is the number of rows and n is the number of columns. We visit each cell at most a constant number of times.
• Space Complexity: O(m × n) in the worst case for the recursion stack (DFS) or the queue (BFS), which occurs when the entire board is filled with 'O's connected to the border.

Best Practices

• Always check for empty input: Guard against null or empty boards before proceeding with any logic.
• Prefer in-place modification: The problem typically requires modifying the board in place to save memory. Avoid creating unnecessary copies.
• Use a temporary marker: Using a character like 'T' that does not appear in the input keeps the logic clean and avoids needing a separate visited set.
• Consider iterative approaches for large inputs: Recursive DFS can cause stack overflow on very large boards. Use BFS or an explicit stack if needed.
• Test edge cases: Boards with all 'X's, all 'O's, single-row boards, and single-column boards should all be tested.
• Optimize the queue: If using BFS, replace shift() with an index-based approach to achieve true O(1) dequeue operations.

Common Pitfalls

• Forgetting diagonal connections: The problem specifies 4-directional connectivity (up, down, left, right). Do not include diagonals unless explicitly stated.
• Missing border checks: Only the outermost rows and columns count as borders. Interior cells, even if adjacent to an 'X', do not qualify.
• Not restoring temporary markers: Forgetting to convert 'T' back to 'O' will leave the board in an invalid state.
• Modifying cells during traversal without marking visited: This can lead to infinite loops or incorrect results.

Conclusion

The Surrounded Regions problem is an excellent exercise in graph traversal and boundary analysis. By applying reverse thinking — marking the cells that should be preserved rather than hunting for those to capture — you arrive at an elegant and efficient solution. Whether you choose DFS or BFS, the core logic remains the same: identify border-connected regions, mark them temporarily, then sweep the board to apply the final transformations. Mastering this problem builds a strong foundation for tackling more complex matrix and graph challenges in your JavaScript development journey.