DEV Community

Cover image for 130. Surrounded Regions πŸš€
Samuel Hinchliffe πŸš€
Samuel Hinchliffe πŸš€

Posted on

130. Surrounded Regions πŸš€


Solution Developed In:

JavaScript

The Question

For this article we will be covering Leetcode's '130. Surrounded Regions' question.

Question:

Given an m x n matrix board containing 'X' and 'O', capture all regions that are 4-directionally > surrounded by 'X'.

A region is captured by flipping all 'O's into 'X's in that surrounded region.

Example

Input: board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output: [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
Explanation: Surrounded regions should not be on the border, which means that any 'O' on the border of the board are not flipped to 'X'. Any 'O' that is not on the border and it is not connected to an 'O' on the border will be flipped to 'X'. Two cells are connected if they are adjacent cells connected horizontally or vertically.
Enter fullscreen mode Exit fullscreen mode

Explaining The Question

This Question is rated Medium. Which is for the most part accurate. But this is ONLY Medium if you have a good grasp of Depth First Search or Breadth First Search on Graph Theory. As well as knowing how to apply these ideas to Matrixes. If you don't know how to do those, you're going to have a difficult time solving this problem.

We've been given a matrix, we're told to capture all regions that do not border the edge of the matrix.
At first glance, this question is simple, run Depth First Search and see if anything borders the edge. If it does, then we know that the region is surrounded. If it doesn't, then we know that the region is not surrounded.


Recommended Knowledge

  1. Graph Theory
  2. Matrixes
  3. Depth First Search

What do we know?

  1. We have a Matrix full of 'X' and 'O'
  2. It's a M x N Matrix
  3. We need to convert all surrounded regions to 'X'

How we're going to do it:

Well we know that all the invalid islands that cannot be surrounded by 'X' are connected to the edges of the matrix. So firstly, we're going to visit all the border of the matrix asking if any of the given nodes are 'O', if they're we already know they're invalid, so we mark the entire island as 'T' meaning temp. As we're going to un-convert them later on.

Once we have marked all the invalid islands, we automatically capture all regions that are not 'T'. All the temp regions are converted back to their original 'O' state.

  1. Run all the edges of the matrix in search for invalid islands.
  2. Perform Depth First Search on the invalid islands and mark the invalid islands as 'T'
  3. Run through the entire matrix and automatically capture all the regions that are not 'T'
  4. Then convert all the 'T' regions back to 'O'

Big O Notation:

  • Time Complexity: O((V * E) + b) / O(n) | Where n is the number of nodes in the Matrix. As we're going to visit every node in the matrix. Where V is the number of nodes in the graph and E is the number of edges in the graph. And where b represents the border of the matrix. As in the worst case, we will visit each node and each one of it's vertexes, which would mean the entire matrix is an island.
  • Space Complexity: O(h) | Where h is the largest number of nodes within a border island, as we will store all of those nodes within the Call Stack to perform our Depth First Search.

The Solution

/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solve = function(board) {

    /* -------------------------------------------------------------------------- */
    /*                          130. Surrounded Regions                           */
    /* -------------------------------------------------------------------------- */

    /* ---------------------------- Solution Concept ---------------------------- */

    // We need to capture all regions that are not bordered to the edge of the matrix.
    // We could perform Depth First Search on all the cells in the matrix and ask
    // if any of them border the edge. Instead, we're going to do all the edges
    // of the matrix and convert all island that border the island to temp nodes.
    // We do this because we already know that the bad nodes border the edge 
    // of the matrix.

    // Once we've marked all the bad islands. We run through the entire matrix
    // automatically capturing all the nodes that are not marked as bad. And all
    // the previously marked bad nodes are converted to back to islands.

    /* ---------------------------- Solution as Code ---------------------------- */

    // Matrix Maxes (Makes our life's easier)
    const max_rows = board.length - 1;
    const max_cols = board[0].length - 1;

    // During our search, we can go up, down, left and right.
    // We cannot go diagonally! We can only go up, down, left and right.
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];

    // Our helper depth first function that converts all bad
    // islands to marked nodes.
    const depth_first_search = (row_index, col_index) => {

        // Is it within bounds of the matrix?
        // And are we allowed to do dfs on this node?
        if (row_index > max_rows || col_index > max_cols || col_index < 0 || row_index < 0 || board[row_index][col_index] != "O"){
            return false
        }

        // So node is within bounds, it bordered the edges of the matrix
        // and thus it's a invalid island. As we cannot Surround the Region
        // So let's mark it as a 't'. We do this to let us know not to 
        // convert this node into a 'x'.

        board[row_index][col_index] = "T";

        // Search in all directions for the rest of the island.
        for (const [x, y] of directions){
            depth_first_search(row_index + x, col_index + y);
        }
    }


    // let's check all the edges of the matrix checking 
    // for these bad nodes. If we ever find one, we run 
    // DFS on it to mark it. Starting with:

    // Top and Bottom of matrix
    for (let i = 0; i <= max_cols ; i++){
        const top = board[0][i];
        const bottom = board[max_rows][i];

        if (top === "O"){
            depth_first_search(0, i);
        }

        if (bottom === "O"){
            depth_first_search(max_rows, i);
        }
    }

    // Left and Right of matrix
    for (let i = 0; i <= max_rows ; i++){
        const left = board[i][0];
        const right = board[i][max_cols];

        if (left === "O"){
            depth_first_search(i, 0);
        }

        if (right === "O"){
            depth_first_search(i, max_cols);
        }
    }

    // Now we have gone through the entire border of the matrix
    // we have now marked all bad islands if their was any.
    // Meaning we can automatically capture all regions that 
    // didn't border that edge.

    // We will also unmark all the marked nodes that did border 
    // the edge of the matrix. We do this because we know that it's an invalid island.
    board.forEach((row, row_index) => {
        row.forEach((col, col_index) => {

            // Capture unmarked regions.
            if (col === "O") board[row_index][col_index] = "X"

            // Converted marked regions back to a normal island
            if (col === "T") board[row_index][col_index] = "O"
        })
    })

    // Return Nothing. We modified our input in place.

};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)