Leetcode - 130. Surrounded Regions

January 30, 2023•1,992 words

The Problem

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.

Link to the problem: https://leetcode.com/problems/surrounded-regions

The solution

So the problem here lies in how to find the regions of 'O's. Once that it's clear, what we need to do is find all the regions of 'O's and check if they're completely surrounded by ' X's.
For all those regions that are surrounded we turn each element into an 'O'.

At this point, I think that to identify the regions of 'O' what we can do is traverse the neighbours of each node.
For that, first, we are going to search for a 'O' in the board.

Finding our first O

const O = "O";
const X = "X";

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

    for(var i = 0; i < m; ++i) {
        for (var j = 0; j < n; ++j) {
            const curr = board[i][j];
            if (curr == O)
            {
                console.log("found it", i, j);
            }
        }
    }
};

When we get to the console.log we have to start identifying the current region so for now, we're going to focus on that, and we're going to create a new function that does that.

Finding our neighbours

const O = "O";
const X = "X";
const directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
];

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

    for(var i = 0; i < m; ++i) {
        for (var j = 0; j < n; ++j) {
            const curr = board[i][j];
            if (curr == O)
            {
                console.log("found it", getRegion(board, i, j));
            }
        }
    }
};

function getRegion(board, i, j) {
    const m = board.length;
    const n = board[0].length;

    const found = [];
    // Initialize found matrix
    for (var row = 0; row < m; ++row) {
        found.push(new Array(n));
    }
    found[i][j] = true //< we "found" our initial node
    const neighbors = [[i,j]]; //< we set our current node as a node to process

    do {
        // Get the next node to process
        let curr = neighbors.shift();

        // check all surrounding nodes
        for (let d = 0; d < directions.length; ++d) {
            const dir = directions[d];
            const y = curr[0] + dir[0];
            const x = curr[1] + dir[1];

            // Ignore the neighbor if it's out of bounds
            if (y < 0 || y >= m ||
                x < 0 || x >= n)
            {
                // TODO: here we know that the regions is not surrounded
                continue;
            }

            // get the neighbor node
            const node = board[y][x];
            if (node == O && !found[y][x]) {
                // If it's an O a we haven't visited it yet
                neighbors.push([y,x]); //< Add it to the neighbors to process
                found[y][x] = true; //< mark it as found
            }
        }
        // Once we have checked all neighbours
        // check if there's any neighbour left to process and repeat
    } while (neighbors.length);

    // Once we're done processing the neighbors we have our region
    return region;
}

I've commented the code but let's go through the important parts of the function.

First we want to get track of the current region so we're going to create a data structure that represents the nodes of the current region. For simplicity we are going to "clone" the board but the elements will be boolean, being true if the node belongs to the region or false otherwise.

Next we are going to define a queue of the nodes we have to process. Again for simplicity we're going to be using a JS Array, but notice that arrays are not optimal queues since the dequeue operation shifts the whole array (and that's why it's called shift :sweat_smile:).
We are going to include the initial node since we want to check the adjacent nodes to that one first.
We're going to be looping until we have no more nodes to process in the neighbors queue.

We dequeue the next element to process and we start checking the surrounding nodes. I've created a helper structure to make it easier to check in every direction.
First we're going to check if the coordinates for the adjacent node are out of bounds. If they are, that means that the current node is in the edge (and thus not surrounded by 'X' but let's keep that aside for now).
If it's not out of bounds, we get the node and if it's an 'O' and we haven seen that node yet, we need to add it to the neighbours queue and mark it as found. This will guarantee us that a node is not processed more than once.

We do this for every neighbor and every direction.

Once we have processed all the nodes we have our region.

So, what next...

Flip the region

So as I was saying before, we need to flip a region if it's surrounded by 'X's, meaning that the regions of 'O's has no node that it's on the edge of the board.
And the magic is, we already know that:

// Ignore the neighbor if it's out of bounds
if (y < 0 || y >= m ||
     x < 0 || x >= n)
{
    // TODO: here we know that the regions is not surrounded
    continue;
}

There we can set a flag that tells us if we should flip the region or not. So lets do it.

function getRegion(board, i, j) {
    const m = board.length;
    const n = board[0].length;

    // We'll assume the "worst" until proven otherwise
    let isSurrounded = true;

    const found = [];
    // Initialize found matrix
    for (var row = 0; row < m; ++row) {
        found.push(new Array(n));
    }
    found[i][j] = true //< we "found" our initial node
    const neighbors = [[i,j]]; //< we set our current node as a node to process

    do {
        // Get the next node to process
        let curr = neighbors.shift();

        // check all surrounding nodes
        for (let d = 0; d < directions.length; ++d) {
            const dir = directions[d];
            const y = curr[0] + dir[0];
            const x = curr[1] + dir[1];

            // Ignore the neighbor if it's out of bounds
            if (y < 0 || y >= m ||
                x < 0 || x >= n)
            {
        // The current node is on the edge, so we're not surrounded
                isSurrounded = false; 
                continue;
            }

            // get the neighbor node
            const node = board[y][x];
            if (node == O && !found[y][x]) {
                // If it's an O a we haven't visited it yet
                neighbors.push([y,x]); //< Add it to the neighbors to process
                found[y][x] = true; //< mark it as found
            }
        }
        // Once we have checked all neighbors
        // check if there's any neighbor left to process and repeat
    } while (neighbors.length);

    // Once we're done processing the neighbors we have our region

    if (isSurrounded) {
    // flip the board given the current region
        flipIt(board, region);
    }

    return region;
}

And there it is, we track if the current region is surrounded, if it is, we call a new function to flip the nodes in the original board.

function flipIt(matrix, mask) {
    const m = matrix.length;
    const n = matrix[0].length;

    // Travel all the matrix like Neo
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (mask[i][j]) // If the node belongs to the region
                matrix[i][j] = X; // flip it!
        }
    }

    // we do not need to return the matrix since it's a reference
    // we are already modifying the original
}

The function is pretty simple since it only involves walking through the whole board and flipping those nodes where the mask (region) is set to true.
Once we've done that the original table will be in it's correct state.

From:

[
    ["X","X","X","X"],
    ["X","O","O","X"],
    ["X","X","O","X"],
    ["X","O","X","X"]
]

To:

[
    ["X","X","X","X"],
    ["X","X","X","X"],
    ["X","X","X","X"],
    ["X","O","X","X"]
]

Housekeeping

So adjusting some names and such the final code would be:

const O = "O";
const X = "X";
const directions = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
]

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

    for(var i = 0; i < m; ++i) {
        for (var j = 0; j < n; ++j) {
            const curr = board[i][j];
            if (curr == O)
                tryFlipRegion(board, i, j);
        }
    }
};

function tryFlipRegion(board, i, j) {
    const m = board.length;
    const n = board[0].length;

    let isSurrounded = true;

    const found = [];
    // Initialize found matrix
    for (var row = 0; row < m; ++row) {
        found.push(new Array(n));
    }
    found[i][j] = true //< we "found" our initial node
    const neighbors = [[i,j]]; //< we set our current node as a node to process

    do {
        // Get the next node to process
        let curr = neighbors.shift();

        // check all surrounding nodes
        for (let d = 0; d < directions.length; ++d) {
            const dir = directions[d];
            const y = curr[0] + dir[0];
            const x = curr[1] + dir[1];

            // Ignore the neighbor if it's out of bounds
            if (y < 0 || y >= m ||
                x < 0 || x >= n)
            {
                isSurrounded = false;
                continue;
            }

            // get the neighbor node
            const node = board[y][x];
            if (node == O && !found[y][x]) {
                // If it's an O a we haven't visited it yet
                neighbors.push([y,x]); //< Add it to the neighbors to process
                found[y][x] = true; //< mark it as found
            }
        }
        // Once we have checked all neighbors
        // check if there's any neighbor left to process and repeat
    } while (neighbors.length);

    // Once we're done processing the neighbors we have our region

    if (isSurrounded) {
        flip(board, found);
    }
}

function flip(matrix, mask) {
    const m = matrix.length;
    const n = matrix[0].length;

    // Travel all the matrix like Neo
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (mask[i][j]) // If the node belongs to the region
                matrix[i][j] = X; // flip it!
        }
    }

    // we do not need to return the matrix since it's a reference
    // we are already modifying the original
}

Improvements

So it's a bit obvious that we're doing some extra work. So there's a bit of improvement over this work.
I'll leave some points that I may or may not try to improve in the future. Maybe you can work on these too.

  1. We are revisiting regions multiple times if we don't flip them. Try to keep a registry in the main function of the nodes we've visited.
  2. We may not need to clone the whole board to define a region.
  3. We may break early of the region if we know we're not going to flip it (but that means we may be processing it again in the future).

Final words

Either if you're learning or trying to prove I'm not smart enough take into consideration this was written while trying to solve the problem by myself without looking anything up using those dang modern AI machines kids these days use. I'll only admit I had to search if it was shift or unshift because that API will always be the bane of my existence.

The problem was submitted and passes, but as stated before it's definitely not the best solution, so try your yourself and see what you can improve.

Take care and be kind!