Surrounded regions

Difficulty: Hard

Asked in: Google

Understanding The Problem

Problem Description

Given a 2-D matrix board where every element is either ‘ O ’ or ‘ X ’ , write a program to replace ‘ O ’ with ‘ X ’ if surrounded by ‘ X ’.

Problem Note

• An ‘ O ’ or a set of ‘ O ’ is considered to be by surrounded by ‘ X ’ if there are ‘ X ’ at locations just below, just above just left and just right of it.
• Surrounded regions shouldn’t 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.

Example 1

Input: board[][] = [ 
                 ['X', 'O', 'X', 'X', 'X', 'X'],
                 ['X', 'O', 'X', 'X', 'O', 'X'],
                 ['X', 'X', 'X', 'O', 'O', 'X'],
                 ['O', 'X', 'X', 'X', 'X', 'X'],
                 ['X', 'X', 'X', 'O', 'X', 'O'],
                 ['O', 'O', 'X', 'O', 'O', 'O'],
               ]
Output: board[][] = [ 
                  ['X', 'O', 'X', 'X', 'X', 'X'],
                  ['X', 'O', 'X', 'X', 'X', 'X'],
                  ['X', 'X', 'X', 'X', 'X', 'X'],
                  ['O', 'X', 'X', 'X', 'X', 'X'],
                  ['X', 'X', 'X', 'O', 'X', 'O'],
                  ['O', 'O', 'X', 'O', 'O', 'O'],
                ]

Example 2

Input: board[][] = [ 
                 ['X', 'X', 'X', 'X']
                 ['X', 'O', 'X', 'X']
                 ['X', 'O', 'O', 'X']
                 ['X', 'O', 'X', 'X']
                 ['X', 'X', 'O', 'O']
               ]
Output: board[][] = [ 
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'X', 'X']
                  ['X', 'X', 'O', 'O']
                ]

Solutions

This problem can be solved by the famous Flood Fill Algorithm . The main difference here is that a 'O' is not replaced by 'X' if it lies in a region that ends on a boundary.

Flood fill algorithm can be simply explained as a graph traversal problem, representing the given area as a matrix and considering every cell of that matrix as a vertex that is connected to points above it, below it, to the right of it, and to the left of it. In general, any cell [x,y] connected with [x-1][y], [x+1][y], [x][y-1], [x][y+1] cells.

For this problem, the flood fill algorithm can be explained as a recursive function that will convert all the mark A with mark B of the input board matrix.

void floodFillUtil(char[][] board, int x, int y, char markA, char markB, int dimsX, int dimsY) 
{ 
    if (x < 0 or x >= dimsX or y < 0 or y >= dimsY) 
        return
    if (board[x][y] != markA)
        return
    // Replace the mark
    board[x][y] = markB
    // Recur for the four directions
    floodFillUtil(board, x+1, y, markA, markB, dimsX, dimsY)
    floodFillUtil(board, x-1, y, markA, markB, dimsX, dimsY)
    floodFillUtil(board, x, y+1, markA, markB, dimsX, dimsY)
    floodFillUtil(board, x, y-1, markA, markB, dimsX, dimsY)
}

So, The idea is very simple, we will convert all the 'O' to '$' . Now we will search for all the ‘$’ at the boundary of the matrix and for each such ‘$’ we will apply the flood fill algorithm to convert them to ‘O’ . In this way, we will be left with all the ‘$’ which will be surrounded by only ‘X’ .

You can try the problem here .

Example 1 can be visualized as

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

convert all O to $
['X', '$', 'X', 'X', 'X', 'X']
['X', '$', 'X', 'X', '$', 'X']
['X', 'X', 'X', '$', '$', 'X']
['$', 'X', 'X', 'X', 'X', 'X']
['X', 'X', 'X', '$', 'X', '$']
['$', '$', 'X', '$', '$', '$']

Choose boundry $ and flood fill them with O
['X', 'O', 'X', 'X', 'X', 'X']
['X', 'O', 'X', 'X', '$', 'X']
['X', 'X', 'X', '$', '$', 'X']
['O', 'X', 'X', 'X', 'X', 'X']
['X', 'X', 'X', 'O', 'X', 'O']
['O', 'O', 'X', 'O', 'O', 'O']

Replace all the $ with X
['X', 'O', 'X', 'X', 'X', 'X']
['X', 'O', 'X', 'X', 'X', 'X']
['X', 'X', 'X', '$', 'X', 'X']
['O', 'X', 'X', 'X', 'X', 'X']
['X', 'X', 'X', 'O', 'X', 'O']
['O', 'O', 'X', 'O', 'O', 'O']

Solution steps

• Create a flood fill function, which recursively marks each node with the input symbol in DFS fashion until it touches the boundary where the boundary will be the end of the matrix or boundary of different symbols.
• Convert each ‘O’ to ‘$’
• Apply flood fill for all the boundary ‘$’ to convert into ‘O’
• Now replace all the left ‘$’ into ‘X’

Pseudo Code

void floodFillUtil(char[][] board, int x, int y, char markA, char markB) 
{ 
    if (x < 0 or x >= board[0].size() or y < 0 or y >= board.size) 
        return
    if (board[x][y] != markA)
        return
    // Replace the mark
    board[x][y] = markB
    // Recur for the four directions
    floodFillUtil(board, x+1, y, markA, markB)
    floodFillUtil(board, x-1, y, markA, markB)
    floodFillUtil(board, x, y+1, markA, markB)
    floodFillUtil(board, x, y-1, markA, markB)
}

void surroundedRegions(char[][] board, int dimsX, dimsY) 
{
    for (int i=0 to i < dimsX) 
        for (int j=0 to j < dimsY) 
            if (board[i][j] is 'O')
                board[i][j] = '$'
    for (int i=0 to i < dimsX)  // Left boundry
        if (board[i][0] is '$') 
            floodFillUtil(board, i, 0, '$', 'O')
    for (int i=0 to i < dimsX)  //  Right boundry
        if (board[i][dimsY - 1] is '$')
            floodFillUtil(board, i, dimsY - 1, '$', 'O')
    for (int i=0 to i<dimsY)   // Top boundry
        if (board[0][i] is '$') 
            floodFillUtil(board, 0, i, '$', 'O')
    for (int i=0; i<dimsY; i++)  // Bottom boundry
        if (board[dimsX - 1][i] is '$') 
            floodFillUtil(board, dimsX - 1, i, '$', 'O')
    for (int i=0 to i < dimsX)
        for (int j=0 to j < dimsY) 
            if (board[i][j] is '$') 
                board[i][j] = 'X'
}

Complexity Analysis

Time Complexity: O(n²)

Space Complexity: O(n²)

where n² is the size of the board matrix.

Critical Ideas To Think

• What does the flood fill algorithm do?
• How come we assumed the matrix as a graph and considered adjacent nodes as connected nodes?
• Why did we first converted all the 'O' into '$'?
• Floodfill acts like a DFS algorithm in the above pseudo-code. Do you think, converting it into a BFS algorithm will affect the solution?

Suggested Problems To Solve

• Number of islands
• Flood fill an image
• Determine the perimeter of the island if 1's in the matrix represent an island and 0's represent water.
• Implement a fill function for the paint's color fill tool.

Please comment down below if you have a better insight in the above approach.

Happy Coding, Enjoy Algorithms!