Jobs

Interviews

Discussions

Surrounded Regions

#51 Most AskedMedium

Surrounded Regions #51 Most Asked

Medium

Nutanix

3 views

Topics:

ArraysGraphs

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every 'O' cell.
Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Example 1:

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:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Try coding it in LeetCode

Surrounded Regions

#51 Most AskedMedium

Surrounded Regions #51 Most Asked

Medium

Nutanix

3 views

Topics:

ArraysGraphs

You are given an m x n matrix board containing letters 'X' and 'O', capture regions that are surrounded:

Connect: A cell is connected to adjacent cells horizontally or vertically.
Region: To form a region connect every 'O' cell.
Surround: The region is surrounded with 'X' cells if you can connect the region with 'X' cells and none of the region cells are on the edge of the board.

To capture a surrounded region, replace all 'O's with 'X's in-place within the original board. You do not need to return anything.

Example 1:

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:

In the above diagram, the bottom region is not captured because it is on the edge of the board and cannot be surrounded.

Example 2:

Input: board = [["X"]]

Output: [["X"]]

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 200
board[i][j] is 'X' or 'O'.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the board (number of rows and columns)? Is it safe to assume both dimensions will always be greater than zero?
What characters can the board contain other than 'X' and 'O'? Can I assume the board will only contain 'X' and 'O' characters?
Should the modification of 'O's to 'X's be done in-place, modifying the original board, or should I return a new board with the changes?
Are the 'O's connected diagonally considered surrounded?
If the board is empty or null, what should I return? Should I throw an exception, return null, or return the empty board itself?

Brute Force Solution

Approach

We're trying to capture regions of 'O's on a grid that are completely surrounded by 'X's. The brute force way is to examine each 'O' on the grid individually and meticulously check if it's surrounded by 'X's.

Here's how the algorithm would work step-by-step:

Look at each position on the grid.
If you find an 'O', start exploring outwards from it in all directions (up, down, left, right).
As you explore, check if you reach the edge of the grid.
If you reach the edge of the grid, it means the 'O' is connected to an 'O' on the boundary, and therefore is not fully surrounded and should be skipped.
If you never reach the edge of the grid and only encounter 'X's during your exploration, then the starting 'O', and all the 'O's connected to it, are fully surrounded by 'X's and should be flipped to 'X's.
Repeat this process for every 'O' on the grid.

Code Implementation

def solve_surrounded_regions(board):
    if not board or not board[0]:
        return

    number_of_rows = len(board)
    number_of_columns = len(board[0])

    def explore_and_flip(row_index, column_index, visited, initial_row, initial_column):
        if row_index < 0 or row_index >= number_of_rows or \
           column_index < 0 or column_index >= number_of_columns or \
           (row_index, column_index) in visited or \
           board[row_index][column_index] == 'X':
            return True

        visited.add((row_index, column_index))

        if row_index == 0 or row_index == number_of_rows - 1 or \
           column_index == 0 or column_index == number_of_columns - 1:
            return False

        up = explore_and_flip(row_index - 1, column_index, visited, initial_row, initial_column)
        down = explore_and_flip(row_index + 1, column_index, visited, initial_row, initial_column)
        left = explore_and_flip(row_index, column_index - 1, visited, initial_row, initial_column)
        right = explore_and_flip(row_index, column_index + 1, visited, initial_row, initial_column)

        return up and down and left and right

    def flip_region(row_index, column_index, flipped):
        if row_index < 0 or row_index >= number_of_rows or \
           column_index < 0 or column_index >= number_of_columns or \
           (row_index, column_index) in flipped or \
           board[row_index][column_index] == 'X':
            return

        flipped.add((row_index, column_index))
        board[row_index] = board[row_index][:column_index] + 'X' + board[row_index][column_index+1:]

        flip_region(row_index - 1, column_index, flipped)
        flip_region(row_index + 1, column_index, flipped)
        flip_region(row_index, column_index - 1, flipped)
        flip_region(row_index, column_index + 1, flipped)

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'O':
                visited_cells = set()
                
                #Checking if region is surrounded
                is_surrounded = explore_and_flip(row_index, column_index, visited_cells, row_index, column_index)
                
                if is_surrounded:
                    flipped_cells = set()

                    #Flip the region
                    flip_region(row_index, column_index, flipped_cells)

Big(O) Analysis

Time Complexity

O(m*n*k) – The algorithm iterates through each cell of the m x n board, resulting in O(m*n). For each 'O' encountered, a depth-first search (DFS) or breadth-first search (BFS) is performed to explore connected 'O's. In the worst-case scenario, the connected component could span a significant portion of the board. The 'k' represents the time to traverse the connected components. Therefore, the overall time complexity becomes O(m*n*k), where k is related to the number of cells visited in the worst-case during exploration from an 'O'.

Space Complexity

O(M * N) – The provided explanation outlines a process where for each 'O' found on the grid, an exploration outwards is performed. This exploration, likely implemented with recursion or a queue (implicit data structure for managing cells to visit), potentially visits every cell connected to the starting 'O'. In the worst-case scenario, a large region of 'O's might require us to keep track of a significant portion of the board's cells during the exploration to avoid revisiting them, commonly tracked with a visited set or directly modifying the input. This means we might need space proportional to the grid's dimensions, where M is the number of rows and N is the number of columns. Thus, the space complexity in the worst case becomes O(M * N).

Optimal Solution

Approach

The goal is to flip 'O's to 'X's in a grid, but only the 'O's that are completely surrounded by 'X's. The clever idea is to start from the edges of the grid and mark the 'O's connected to the edges as safe, then flip the rest.

Here's how the algorithm would work step-by-step:

Imagine you have a grid full of 'X's and 'O's. You want to change all the 'O's that are trapped to 'X's, but 'O's connected to the edge should stay 'O's.
Find all the 'O's that are on the very edge of the grid. These are definitely safe because they're not surrounded.
From those edge 'O's, find all the other 'O's that are connected to them, going up, down, left, and right. Think of it like water spreading out from the edges. Mark all these connected 'O's as safe too - give them a special temporary mark.
Now, go through every cell in the grid. Any 'O's that are still 'O's (meaning they weren't marked as safe) must be surrounded, so change them to 'X's.
Finally, change the specially marked safe 'O's back to regular 'O's. Now you have your final grid with the surrounded 'O's flipped.

Code Implementation

def solve_surrounded_regions(board):
    if not board:
        return

    number_of_rows = len(board)
    number_of_columns = len(board[0])

    def depth_first_search(row, column):
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           board[row][column] != 'O':
            return

        board[row][column] = 'T'

        depth_first_search(row + 1, column)
        depth_first_search(row - 1, column)
        depth_first_search(row, column + 1)
        depth_first_search(row, column - 1)

    # Iterate through the edges and mark connected 'O's as 'T'
    for row_index in range(number_of_rows):
        if board[row_index][0] == 'O':
            depth_first_search(row_index, 0)
        if board[row_index][number_of_columns - 1] == 'O':
            depth_first_search(row_index, number_of_columns - 1)

    for column_index in range(number_of_columns):
        if board[0][column_index] == 'O':
            depth_first_search(0, column_index)
        if board[number_of_rows - 1][column_index] == 'O':
            depth_first_search(number_of_rows - 1, column_index)

    # Capture all 'O's that were not connected to the edge
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'O':
                board[row_index][column_index] = 'X'

            # Revert temporary 'T's back to 'O's
            if board[row_index][column_index] == 'T':
                board[row_index][column_index] = 'O'

    # After processing, the board is modified in-place,
    # no explicit return is needed.
    return board

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm first iterates through the edges of the m x n board to find 'O's, which takes O(m + n) time. From each of these 'O's, it performs a Depth-First Search (DFS) to identify all connected 'O's. In the worst case, the DFS might visit every cell in the board, taking O(m*n) time. Finally, the algorithm iterates through the entire board twice, once to flip the remaining 'O's to 'X's and again to revert the temporary markers back to 'O's; each of these passes takes O(m*n) time. Thus, the dominant factor is the potential DFS traversal of all cells resulting in a time complexity of O(m*n).

Space Complexity

O(m*n) – The algorithm uses a queue (implicitly in step 3) to perform a breadth-first search (BFS) to find all 'O's connected to the edge. In the worst-case scenario, where the entire grid is filled with 'O's, the queue could contain all the cells of the board. Therefore, the auxiliary space used by the queue is proportional to the number of cells in the grid, where m is the number of rows and n is the number of columns. This leads to a space complexity of O(m*n).

Edge Cases

Case	How to Handle
Null or empty board	Return immediately if the board is null or has zero rows or columns.
Board with only one row or one column	If the board has only one row or column, 'O's on the border are already connected and should not be flipped, therefore, no action should be taken.
Board filled entirely with 'X's	No 'O's exist so no changes are required and the board remains as is.
Board filled entirely with 'O's	All 'O's except those on the boundary should be flipped to 'X'.
Board with 'O's clustered in the middle, completely surrounded by 'X's	These 'O's should be flipped to 'X's.
Board with 'O's connected to the boundary	These 'O's and any 'O's they connect to should be treated as safe and remain 'O's.
Very large board (memory constraints)	Ensure that the algorithm uses in-place modification to avoid excessive memory usage and prevent potential out-of-memory errors.
Deep recursion with many connected 'O's to the boundary (stack overflow)	Use an iterative approach (e.g., using a queue) instead of recursion to explore connected components and avoid potential stack overflow errors on very large boards.

Null or empty board

How to Handle:

Return immediately if the board is null or has zero rows or columns.

Board with only one row or one column

How to Handle:

If the board has only one row or column, 'O's on the border are already connected and should not be flipped, therefore, no action should be taken.

Board filled entirely with 'X's

How to Handle:

No 'O's exist so no changes are required and the board remains as is.

Board filled entirely with 'O's

How to Handle:

All 'O's except those on the boundary should be flipped to 'X'.

Board with 'O's clustered in the middle, completely surrounded by 'X's

How to Handle:

These 'O's should be flipped to 'X's.

Board with 'O's connected to the boundary

How to Handle:

These 'O's and any 'O's they connect to should be treated as safe and remain 'O's.

Very large board (memory constraints)

How to Handle:

Ensure that the algorithm uses in-place modification to avoid excessive memory usage and prevent potential out-of-memory errors.

Deep recursion with many connected 'O's to the boundary (stack overflow)

How to Handle:

Use an iterative approach (e.g., using a queue) instead of recursion to explore connected components and avoid potential stack overflow errors on very large boards.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the board (number of rows and columns)? Is it safe to assume both dimensions will always be greater than zero?
What characters can the board contain other than 'X' and 'O'? Can I assume the board will only contain 'X' and 'O' characters?
Should the modification of 'O's to 'X's be done in-place, modifying the original board, or should I return a new board with the changes?
Are the 'O's connected diagonally considered surrounded?
If the board is empty or null, what should I return? Should I throw an exception, return null, or return the empty board itself?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each position on the grid.
If you find an 'O', start exploring outwards from it in all directions (up, down, left, right).
As you explore, check if you reach the edge of the grid.
If you reach the edge of the grid, it means the 'O' is connected to an 'O' on the boundary, and therefore is not fully surrounded and should be skipped.
If you never reach the edge of the grid and only encounter 'X's during your exploration, then the starting 'O', and all the 'O's connected to it, are fully surrounded by 'X's and should be flipped to 'X's.
Repeat this process for every 'O' on the grid.

Code Implementation

def solve_surrounded_regions(board):
    if not board or not board[0]:
        return

    number_of_rows = len(board)
    number_of_columns = len(board[0])

    def explore_and_flip(row_index, column_index, visited, initial_row, initial_column):
        if row_index < 0 or row_index >= number_of_rows or \
           column_index < 0 or column_index >= number_of_columns or \
           (row_index, column_index) in visited or \
           board[row_index][column_index] == 'X':
            return True

        visited.add((row_index, column_index))

        if row_index == 0 or row_index == number_of_rows - 1 or \
           column_index == 0 or column_index == number_of_columns - 1:
            return False

        up = explore_and_flip(row_index - 1, column_index, visited, initial_row, initial_column)
        down = explore_and_flip(row_index + 1, column_index, visited, initial_row, initial_column)
        left = explore_and_flip(row_index, column_index - 1, visited, initial_row, initial_column)
        right = explore_and_flip(row_index, column_index + 1, visited, initial_row, initial_column)

        return up and down and left and right

    def flip_region(row_index, column_index, flipped):
        if row_index < 0 or row_index >= number_of_rows or \
           column_index < 0 or column_index >= number_of_columns or \
           (row_index, column_index) in flipped or \
           board[row_index][column_index] == 'X':
            return

        flipped.add((row_index, column_index))
        board[row_index] = board[row_index][:column_index] + 'X' + board[row_index][column_index+1:]

        flip_region(row_index - 1, column_index, flipped)
        flip_region(row_index + 1, column_index, flipped)
        flip_region(row_index, column_index - 1, flipped)
        flip_region(row_index, column_index + 1, flipped)

    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'O':
                visited_cells = set()
                
                #Checking if region is surrounded
                is_surrounded = explore_and_flip(row_index, column_index, visited_cells, row_index, column_index)
                
                if is_surrounded:
                    flipped_cells = set()

                    #Flip the region
                    flip_region(row_index, column_index, flipped_cells)

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you have a grid full of 'X's and 'O's. You want to change all the 'O's that are trapped to 'X's, but 'O's connected to the edge should stay 'O's.
Find all the 'O's that are on the very edge of the grid. These are definitely safe because they're not surrounded.
From those edge 'O's, find all the other 'O's that are connected to them, going up, down, left, and right. Think of it like water spreading out from the edges. Mark all these connected 'O's as safe too - give them a special temporary mark.
Now, go through every cell in the grid. Any 'O's that are still 'O's (meaning they weren't marked as safe) must be surrounded, so change them to 'X's.
Finally, change the specially marked safe 'O's back to regular 'O's. Now you have your final grid with the surrounded 'O's flipped.

Code Implementation

def solve_surrounded_regions(board):
    if not board:
        return

    number_of_rows = len(board)
    number_of_columns = len(board[0])

    def depth_first_search(row, column):
        if row < 0 or row >= number_of_rows or \
           column < 0 or column >= number_of_columns or \
           board[row][column] != 'O':
            return

        board[row][column] = 'T'

        depth_first_search(row + 1, column)
        depth_first_search(row - 1, column)
        depth_first_search(row, column + 1)
        depth_first_search(row, column - 1)

    # Iterate through the edges and mark connected 'O's as 'T'
    for row_index in range(number_of_rows):
        if board[row_index][0] == 'O':
            depth_first_search(row_index, 0)
        if board[row_index][number_of_columns - 1] == 'O':
            depth_first_search(row_index, number_of_columns - 1)

    for column_index in range(number_of_columns):
        if board[0][column_index] == 'O':
            depth_first_search(0, column_index)
        if board[number_of_rows - 1][column_index] == 'O':
            depth_first_search(number_of_rows - 1, column_index)

    # Capture all 'O's that were not connected to the edge
    for row_index in range(number_of_rows):
        for column_index in range(number_of_columns):
            if board[row_index][column_index] == 'O':
                board[row_index][column_index] = 'X'

            # Revert temporary 'T's back to 'O's
            if board[row_index][column_index] == 'T':
                board[row_index][column_index] = 'O'

    # After processing, the board is modified in-place,
    # no explicit return is needed.
    return board

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty board	Return immediately if the board is null or has zero rows or columns.
Board with only one row or one column	If the board has only one row or column, 'O's on the border are already connected and should not be flipped, therefore, no action should be taken.
Board filled entirely with 'X's	No 'O's exist so no changes are required and the board remains as is.
Board filled entirely with 'O's	All 'O's except those on the boundary should be flipped to 'X'.
Board with 'O's clustered in the middle, completely surrounded by 'X's	These 'O's should be flipped to 'X's.
Board with 'O's connected to the boundary	These 'O's and any 'O's they connect to should be treated as safe and remain 'O's.
Very large board (memory constraints)	Ensure that the algorithm uses in-place modification to avoid excessive memory usage and prevent potential out-of-memory errors.
Deep recursion with many connected 'O's to the boundary (stack overflow)	Use an iterative approach (e.g., using a queue) instead of recursion to explore connected components and avoid potential stack overflow errors on very large boards.

Null or empty board

How to Handle:

Return immediately if the board is null or has zero rows or columns.

Board with only one row or one column

How to Handle:

If the board has only one row or column, 'O's on the border are already connected and should not be flipped, therefore, no action should be taken.

Board filled entirely with 'X's

How to Handle:

No 'O's exist so no changes are required and the board remains as is.

Board filled entirely with 'O's

How to Handle:

All 'O's except those on the boundary should be flipped to 'X'.

Board with 'O's clustered in the middle, completely surrounded by 'X's

How to Handle:

These 'O's should be flipped to 'X's.

Board with 'O's connected to the boundary

How to Handle:

These 'O's and any 'O's they connect to should be treated as safe and remain 'O's.

Very large board (memory constraints)

How to Handle:

Ensure that the algorithm uses in-place modification to avoid excessive memory usage and prevent potential out-of-memory errors.

Deep recursion with many connected 'O's to the boundary (stack overflow)

How to Handle:

Use an iterative approach (e.g., using a queue) instead of recursion to explore connected components and avoid potential stack overflow errors on very large boards.

0/66 Nutanix questions completed

0/66 completed