Jobs

Interviews

Discussions

Number of Enclaves

Medium

Amazon

1 view

Topics:

ArraysGraphsDynamic Programming

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

For example:

grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output: 3

Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because it is on the boundary.

As another example:

grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output: 0

Explanation: All 1s are either on the boundary or can reach the boundary.

Can you provide an algorithm to efficiently determine the number of land cells that cannot walk off the boundary of the grid? What is the time and space complexity of your solution?

Number of Enclaves

Medium

Amazon

1 view

Topics:

ArraysGraphsDynamic Programming

You are given an m x n binary matrix grid, where 0 represents a sea cell and 1 represents a land cell.

A move consists of walking from one land cell to another adjacent (4-directionally) land cell or walking off the boundary of the grid.

Return the number of land cells in grid for which we cannot walk off the boundary of the grid in any number of moves.

For example:

grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]

Output: 3

Explanation: There are three 1s that are enclosed by 0s, and one 1 that is not enclosed because it is on the boundary.

As another example:

grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]

Output: 0

Explanation: All 1s are either on the boundary or can reach the boundary.

Can you provide an algorithm to efficiently determine the number of land cells that cannot walk off the boundary of the grid? What is the time and space complexity of your solution?

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 grid, and what are the maximum possible values for `m` and `n`?
What values can the grid cells contain? Is it guaranteed to be only 0 and 1?
If the grid is empty or null, what should I return?
Are cells connected only horizontally and vertically, or also diagonally?
Could you define more precisely what constitutes an 'enclave'? Specifically, does a single '1' surrounded by '0's count as an enclave?

Brute Force Solution

Approach

The goal is to find landlocked regions in a map of land and water. The brute force method explores the entire map to identify these regions by meticulously examining each land cell. It checks if each land cell is completely surrounded by water, or if it connects to the edge of the map.

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

Look at each piece of land, one at a time.
For each piece of land, check all the spots directly around it to see if they're water.
If any of those spots are also land, check the spots around that land too, and keep going until you've checked all connected land.
If at any point during your checks you reach the edge of the map, that original piece of land and all the land connected to it are NOT part of an enclosed region.
If after checking all connected land, you never reach the edge of the map, that entire region is enclosed.
Count up all the pieces of land that are part of an enclosed region. That's your answer.

Code Implementation

def number_of_enclaves_brute_force(grid): 
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    enclaves_count = 0

    def explore_land(row, column, visited): 
        if (row < 0 or row >= number_of_rows or column < 0 or \
            column >= number_of_columns or (row, column) in visited or \
            grid[row][column] == 0):
            return True

        visited.add((row, column))

        # If we hit the edge, it's not an enclave
        if row == 0 or row == number_of_rows - 1 or column == 0 or \
           column == number_of_columns - 1:
            return False

        # Recursively explore adjacent land cells
        up = explore_land(row - 1, column, visited)
        down = explore_land(row + 1, column, visited)
        left = explore_land(row, column - 1, visited)
        right = explore_land(row, column + 1, visited)

        return up and down and left and right

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                visited_cells = set()

                # Check if land cell is part of an enclave
                is_enclave = explore_land(row, column, visited_cells)

                if is_enclave:
                    # If it is, add its land cells to the total count
                    for row_visited, column_visited in visited_cells:
                        enclaves_count += 1

    return enclaves_count

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each cell of the m x n grid. For each land cell encountered, a depth-first search (DFS) or breadth-first search (BFS) explores all connected land cells. In the worst-case scenario, the entire grid consists of land, and the algorithm explores all m*n cells for each connected component. Thus, the overall time complexity is O(m*n), where m and n are the dimensions of the grid.

Space Complexity

O(M * N) – The algorithm uses a depth-first search (DFS) or breadth-first search (BFS) approach to explore connected land cells. To avoid revisiting cells, it implicitly maintains a 'visited' set or modifies the input grid in place. In the worst-case scenario, the entire grid consists of land, and the algorithm would explore all M * N cells where M is the number of rows and N is the number of columns. This means the recursion stack for DFS or the queue for BFS can grow to the size of the grid, leading to O(M * N) auxiliary space. Therefore, the auxiliary space complexity is O(M * N), where M and N are the dimensions of the grid.

Optimal Solution

Approach

The goal is to find land cells that are completely surrounded by water. The clever approach is to identify and eliminate land cells that are connected to the edge, since they are not enclosed and thus are not enclaves.

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

Imagine the grid as a map. Start by looking at all the land cells that are touching the edges of the map.
Treat these edge land cells as the starting point. Explore all the land that's connected to them, like finding all connected land areas on a map.
Mark all the land cells you found in the previous step as 'not part of an enclave' because they are connected to the edge.
Finally, count the remaining land cells that haven't been marked. These are the land cells completely surrounded by water, the enclaves.

Code Implementation

def number_of_enclaves(grid):
    rows = len(grid)
    cols = len(grid[0])

    def depth_first_search(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
            return

        grid[row][col] = 0 # Mark as visited

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

    #Eliminate land connected to edges
    for row_index in range(rows):
        for col_index in range(cols):
            if row_index in [0, rows - 1] or col_index in [0, cols - 1]:
                if grid[row_index][col_index] == 1:

                    depth_first_search(row_index, col_index)

    enclaves_count = 0
    for row_index in range(rows):
        for col_index in range(cols):
            if grid[row_index][col_index] == 1:
                enclaves_count += 1

    return enclaves_count

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through the border of the grid, which has a length proportional to m + n, where m is the number of rows and n is the number of columns. From each border land cell, a Depth-First Search (DFS) or Breadth-First Search (BFS) is performed to identify connected land cells. In the worst case, the DFS/BFS might visit every land cell in the grid, which is O(m * n). Since the border traversal is dominated by the potential full grid traversal during the DFS/BFS, the overall time complexity is O(m * n), where m is the number of rows and n is the number of columns in the grid. The final counting of remaining land cells also takes O(m * n) time but doesn't affect the overall asymptotic complexity.

Space Complexity

O(N) – The space complexity is dominated by the queue or stack used for the breadth-first search (BFS) or depth-first search (DFS) in step 2, where N is the number of cells in the grid. In the worst-case scenario, where a large connected component of land extends from the edge and covers almost the entire grid, the queue or stack could hold a significant portion of the grid cells. Additionally, the marking of visited land cells (step 3) can be done in-place, but if a separate visited set/matrix is used, it will take O(N) space. Therefore, the auxiliary space required is proportional to the size of the grid.

Edge Cases

Case	How to Handle
Null or empty input grid	Return 0 if the grid is null or has zero rows/columns, indicating no enclaves exist.
Grid with only one row or one column	All land cells are on the border, thus return 0 as no enclaves can exist.
Grid filled entirely with water (all 0s)	Return 0 as there are no land cells to form enclaves.
Grid filled entirely with land (all 1s)	Return 0 as all land cells are connected to the boundary.
Large grid with many land cells forming one massive connected component to the edge	The DFS/BFS might require significant stack space; consider iterative BFS to avoid potential stack overflow.
Grid with disconnected land cells that are all enclaves	The algorithm should correctly identify and count all such disconnected enclosed regions.
Integer overflow during grid size calculations.	Ensure grid dimensions are within safe integer limits to prevent overflow when calculating sizes or iterating.
Grid with shapes that are touching an edge at a single point (corner)	These are not considered enclaves since they are connected, and the solution should not count them

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 grid, and what are the maximum possible values for `m` and `n`?
What values can the grid cells contain? Is it guaranteed to be only 0 and 1?
If the grid is empty or null, what should I return?
Are cells connected only horizontally and vertically, or also diagonally?
Could you define more precisely what constitutes an 'enclave'? Specifically, does a single '1' surrounded by '0's count as an enclave?

Brute Force Solution

Approach

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

Look at each piece of land, one at a time.
For each piece of land, check all the spots directly around it to see if they're water.
If any of those spots are also land, check the spots around that land too, and keep going until you've checked all connected land.
If at any point during your checks you reach the edge of the map, that original piece of land and all the land connected to it are NOT part of an enclosed region.
If after checking all connected land, you never reach the edge of the map, that entire region is enclosed.
Count up all the pieces of land that are part of an enclosed region. That's your answer.

Code Implementation

def number_of_enclaves_brute_force(grid): 
    number_of_rows = len(grid)
    number_of_columns = len(grid[0])
    enclaves_count = 0

    def explore_land(row, column, visited): 
        if (row < 0 or row >= number_of_rows or column < 0 or \
            column >= number_of_columns or (row, column) in visited or \
            grid[row][column] == 0):
            return True

        visited.add((row, column))

        # If we hit the edge, it's not an enclave
        if row == 0 or row == number_of_rows - 1 or column == 0 or \
           column == number_of_columns - 1:
            return False

        # Recursively explore adjacent land cells
        up = explore_land(row - 1, column, visited)
        down = explore_land(row + 1, column, visited)
        left = explore_land(row, column - 1, visited)
        right = explore_land(row, column + 1, visited)

        return up and down and left and right

    for row in range(number_of_rows):
        for column in range(number_of_columns):
            if grid[row][column] == 1:
                visited_cells = set()

                # Check if land cell is part of an enclave
                is_enclave = explore_land(row, column, visited_cells)

                if is_enclave:
                    # If it is, add its land cells to the total count
                    for row_visited, column_visited in visited_cells:
                        enclaves_count += 1

    return enclaves_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Imagine the grid as a map. Start by looking at all the land cells that are touching the edges of the map.
Treat these edge land cells as the starting point. Explore all the land that's connected to them, like finding all connected land areas on a map.
Mark all the land cells you found in the previous step as 'not part of an enclave' because they are connected to the edge.
Finally, count the remaining land cells that haven't been marked. These are the land cells completely surrounded by water, the enclaves.

Code Implementation

def number_of_enclaves(grid):
    rows = len(grid)
    cols = len(grid[0])

    def depth_first_search(row, col):
        if row < 0 or row >= rows or col < 0 or col >= cols or grid[row][col] != 1:
            return

        grid[row][col] = 0 # Mark as visited

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

    #Eliminate land connected to edges
    for row_index in range(rows):
        for col_index in range(cols):
            if row_index in [0, rows - 1] or col_index in [0, cols - 1]:
                if grid[row_index][col_index] == 1:

                    depth_first_search(row_index, col_index)

    enclaves_count = 0
    for row_index in range(rows):
        for col_index in range(cols):
            if grid[row_index][col_index] == 1:
                enclaves_count += 1

    return enclaves_count

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input grid	Return 0 if the grid is null or has zero rows/columns, indicating no enclaves exist.
Grid with only one row or one column	All land cells are on the border, thus return 0 as no enclaves can exist.
Grid filled entirely with water (all 0s)	Return 0 as there are no land cells to form enclaves.
Grid filled entirely with land (all 1s)	Return 0 as all land cells are connected to the boundary.
Large grid with many land cells forming one massive connected component to the edge	The DFS/BFS might require significant stack space; consider iterative BFS to avoid potential stack overflow.
Grid with disconnected land cells that are all enclaves	The algorithm should correctly identify and count all such disconnected enclosed regions.
Integer overflow during grid size calculations.	Ensure grid dimensions are within safe integer limits to prevent overflow when calculating sizes or iterating.
Grid with shapes that are touching an edge at a single point (corner)	These are not considered enclaves since they are connected, and the solution should not count them