Jobs

Interviews

Discussions

Shortest Bridge

Medium

Asked by:

22 views

Topics:

ArraysGraphs

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] is either 0 or 1.
There are exactly two islands in grid.

Shortest Bridge

Medium

Asked by:

22 views

Topics:

ArraysGraphs

You are given an n x n binary matrix grid where 1 represents land and 0 represents water.

An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid.

You may change 0's to 1's to connect the two islands to form one island.

Return the smallest number of 0's you must flip to connect the two islands.

Example 1:

Input: grid = [[0,1],[1,0]]
Output: 1

Example 2:

Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2

Example 3:

Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1

Constraints:

n == grid.length == grid[i].length
2 <= n <= 100
grid[i][j] is either 0 or 1.
There are exactly two islands in grid.

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 is the maximum possible dimension? Is it safe to assume the grid will always be square?
What values are possible in the grid? Is it strictly 0 and 1, or could there be other values?
If there are multiple valid shortest bridges, is any one acceptable, or is there a specific criteria for choosing one?
Is it guaranteed that there are exactly two islands in the grid, or could there be fewer (e.g., only one island or none) or more?
If no bridge can be formed (e.g., only one island exists), what value should I return?

Brute Force Solution

Approach

The brute force approach to finding the shortest bridge between two islands treats it like exploring every possible path. We try all possible combinations of starting points on one island and ending points on the other, measuring the distance for each combination. By checking every possibility, we guarantee we find the shortest distance.

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

Find all the land cells that make up the first island.
Find all the land cells that make up the second island.
For every land cell on the first island, calculate its distance to every land cell on the second island.
Keep track of the shortest distance found between any two land cells from different islands.
The shortest distance found will be the answer.

Code Implementation

def shortest_bridge_brute_force(grid):    grid_rows = len(grid)
    grid_cols = len(grid[0])

    first_island_cells = []
    second_island_cells = []
    island_found = False

    def depth_first_search(row, col, island_cells):
        if row < 0 or row >= grid_rows or col < 0 or col >= grid_cols or grid[row][col] == 0 or (row, col) in island_cells:
            return
        
        island_cells.add((row, col))
        depth_first_search(row + 1, col, island_cells)
        depth_first_search(row - 1, col, island_cells)
        depth_first_search(row, col + 1, island_cells)
        depth_first_search(row, col - 1, island_cells)

    # Find the islands using Depth First Search
    for row in range(grid_rows):
        for col in range(grid_cols):
            if grid[row][col] == 1:
                if not island_found:
                    depth_first_search(row, col, first_island_cells)
                    island_found = True
                else:
                    depth_first_search(row, col, second_island_cells)
                    break
        if len(second_island_cells) > 0:
            break

    # Convert sets to lists for indexing
    first_island_cells = list(first_island_cells)
    second_island_cells = list(second_island_cells)

    shortest_distance = float('inf')

    # Calculate distances between islands
    for first_island_index in range(len(first_island_cells)):
        for second_island_index in range(len(second_island_cells)):

            first_island_row = first_island_cells[first_island_index][0]
            first_island_col = first_island_cells[first_island_index][1]
            second_island_row = second_island_cells[second_island_index][0]
            second_island_col = second_island_cells[second_island_index][1]

            # Calculate Manhattan Distance
            distance = abs(first_island_row - second_island_row) + abs(first_island_col - second_island_col) - 1

            # Get the shortest distance between all cells
            shortest_distance = min(shortest_distance, distance)

    return shortest_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n^4) – Let n be the number of cells in the grid. Finding the land cells of the first island takes O(n) in the worst case as we might need to scan all cells. Similarly, finding the land cells of the second island also takes O(n). Once we have the two sets of land cells, say of size k1 and k2 respectively, we iterate through each cell in the first set and compute its distance to every cell in the second set. In the worst-case scenario, k1 and k2 can both be proportional to n, so computing the distances takes O(n*n) time. The overall operation then takes O(n*n*n*n) = O(n^4) in total to compute the shortest bridge given that we might have an amount of n number of land cells to potentially look for in our islands.

Space Complexity

O(N) – The brute force approach involves identifying all land cells in both islands. This requires, at worst, storing every cell of the grid in temporary lists representing the first and second islands respectively. Where N is the number of cells in the grid, the auxiliary space needed to store these cells could approach N in the worst-case scenario, specifically if all cells are land. Therefore, the space complexity is O(N).

Optimal Solution

Approach

The goal is to find the shortest path to connect two islands. We can do this efficiently by first finding one island, then expanding outwards from that island like ripples in a pond until we reach the other island.

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

Find one of the islands on the map.
Mark all the land cells of this island as visited.
Imagine expanding the island one layer at a time, like adding a ring of water around it.
Keep adding layers until you touch the other island.
The number of layers you added is the length of the shortest bridge.

Code Implementation

def shortest_bridge(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()

    def invalid_cell(row, col):
        return row < 0 or row >= rows or col < 0 or col >= cols

    def find_island(row, col):
        if invalid_cell(row, col) or grid[row][col] == 0 or (row, col) in visited:
            return

        visited.add((row, col))
        
        find_island(row + 1, col)
        find_island(row - 1, col)
        find_island(row, col + 1)
        find_island(row, col - 1)

    def find_first_island():
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    find_island(row, col)
                    return

    find_first_island()

    queue = list(visited)
    bridge_length = 0

    # We need to expand the island until we find the other island.
    while queue:
        new_queue = []
        for row, col in queue:
            for new_row, new_col in [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]:
                if invalid_cell(new_row, new_col) or (new_row, new_col) in visited:
                    continue

                if grid[new_row][new_col] == 1:
                    # We've reached the second island.
                    return bridge_length
                
                visited.add((new_row, new_col))
                new_queue.append((new_row, new_col))

        queue = new_queue
        bridge_length += 1

    return -1 # No bridge found

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(n²) – The algorithm explores the grid to find the first island using depth-first search (DFS). In the worst case, the DFS visits every cell of the grid, which is O(n²), where n is the side length of the grid. The breadth-first search (BFS) expands from the first island until the second island is reached, potentially visiting every cell in the grid. Therefore, the overall time complexity, dominated by potentially visiting all cells during DFS and BFS, is O(n²).

Space Complexity

O(N) – The space complexity is dominated by the queue used for the breadth-first search (BFS) expansion. In the worst-case scenario, where one island nearly fills the entire grid, the queue could contain close to all cells of the grid. Also, the visited set to mark the land cells of the first island could store almost all cells. Therefore, where N is the total number of cells in the grid, the space required for BFS queue and the visited cells can grow up to O(N).

Edge Cases

Case	How to Handle
Null or empty input grid	Return 0 immediately, as no bridge can be formed.
Grid with only one cell (1x1)	Return 0, as no bridge is needed; there's only one land mass.
Grid with all 0s (no land)	Return 0, as no bridge can be formed between non-existent islands.
Grid with all 1s (one large island)	Return 0, as no bridge is needed because it's a single island.
Two islands are directly adjacent (distance 0)	The BFS/DFS will correctly identify the two islands and return 0 since no bridge needs building.
Large grid sizes approaching memory limits	The BFS/DFS algorithm could consume significant memory for very large grids, potentially leading to memory errors; consider iterative deepening DFS if memory becomes an issue.
Integer overflow during distance calculation with very large grids	Use `long` type for distance or level counts if grid size is very large to prevent integer overflows when counting distance.
The two islands are diagonally adjacent and need a bridge of length 1.	BFS should correctly consider the diagonal neighbors and find the shortest path of length 1.

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 is the maximum possible dimension? Is it safe to assume the grid will always be square?
What values are possible in the grid? Is it strictly 0 and 1, or could there be other values?
If there are multiple valid shortest bridges, is any one acceptable, or is there a specific criteria for choosing one?
Is it guaranteed that there are exactly two islands in the grid, or could there be fewer (e.g., only one island or none) or more?
If no bridge can be formed (e.g., only one island exists), what value should I return?

Brute Force Solution

Approach

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

Find all the land cells that make up the first island.
Find all the land cells that make up the second island.
For every land cell on the first island, calculate its distance to every land cell on the second island.
Keep track of the shortest distance found between any two land cells from different islands.
The shortest distance found will be the answer.

Code Implementation

def shortest_bridge_brute_force(grid):    grid_rows = len(grid)
    grid_cols = len(grid[0])

    first_island_cells = []
    second_island_cells = []
    island_found = False

    def depth_first_search(row, col, island_cells):
        if row < 0 or row >= grid_rows or col < 0 or col >= grid_cols or grid[row][col] == 0 or (row, col) in island_cells:
            return
        
        island_cells.add((row, col))
        depth_first_search(row + 1, col, island_cells)
        depth_first_search(row - 1, col, island_cells)
        depth_first_search(row, col + 1, island_cells)
        depth_first_search(row, col - 1, island_cells)

    # Find the islands using Depth First Search
    for row in range(grid_rows):
        for col in range(grid_cols):
            if grid[row][col] == 1:
                if not island_found:
                    depth_first_search(row, col, first_island_cells)
                    island_found = True
                else:
                    depth_first_search(row, col, second_island_cells)
                    break
        if len(second_island_cells) > 0:
            break

    # Convert sets to lists for indexing
    first_island_cells = list(first_island_cells)
    second_island_cells = list(second_island_cells)

    shortest_distance = float('inf')

    # Calculate distances between islands
    for first_island_index in range(len(first_island_cells)):
        for second_island_index in range(len(second_island_cells)):

            first_island_row = first_island_cells[first_island_index][0]
            first_island_col = first_island_cells[first_island_index][1]
            second_island_row = second_island_cells[second_island_index][0]
            second_island_col = second_island_cells[second_island_index][1]

            # Calculate Manhattan Distance
            distance = abs(first_island_row - second_island_row) + abs(first_island_col - second_island_col) - 1

            # Get the shortest distance between all cells
            shortest_distance = min(shortest_distance, distance)

    return shortest_distance

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Find one of the islands on the map.
Mark all the land cells of this island as visited.
Imagine expanding the island one layer at a time, like adding a ring of water around it.
Keep adding layers until you touch the other island.
The number of layers you added is the length of the shortest bridge.

Code Implementation

def shortest_bridge(grid):
    rows = len(grid)
    cols = len(grid[0])
    visited = set()

    def invalid_cell(row, col):
        return row < 0 or row >= rows or col < 0 or col >= cols

    def find_island(row, col):
        if invalid_cell(row, col) or grid[row][col] == 0 or (row, col) in visited:
            return

        visited.add((row, col))
        
        find_island(row + 1, col)
        find_island(row - 1, col)
        find_island(row, col + 1)
        find_island(row, col - 1)

    def find_first_island():
        for row in range(rows):
            for col in range(cols):
                if grid[row][col] == 1:
                    find_island(row, col)
                    return

    find_first_island()

    queue = list(visited)
    bridge_length = 0

    # We need to expand the island until we find the other island.
    while queue:
        new_queue = []
        for row, col in queue:
            for new_row, new_col in [(row + 1, col), (row - 1, col), (row, col + 1), (row, col - 1)]:
                if invalid_cell(new_row, new_col) or (new_row, new_col) in visited:
                    continue

                if grid[new_row][new_col] == 1:
                    # We've reached the second island.
                    return bridge_length
                
                visited.add((new_row, new_col))
                new_queue.append((new_row, new_col))

        queue = new_queue
        bridge_length += 1

    return -1 # No bridge found

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty input grid	Return 0 immediately, as no bridge can be formed.
Grid with only one cell (1x1)	Return 0, as no bridge is needed; there's only one land mass.
Grid with all 0s (no land)	Return 0, as no bridge can be formed between non-existent islands.
Grid with all 1s (one large island)	Return 0, as no bridge is needed because it's a single island.
Two islands are directly adjacent (distance 0)	The BFS/DFS will correctly identify the two islands and return 0 since no bridge needs building.
Large grid sizes approaching memory limits	The BFS/DFS algorithm could consume significant memory for very large grids, potentially leading to memory errors; consider iterative deepening DFS if memory becomes an issue.
Integer overflow during distance calculation with very large grids	Use `long` type for distance or level counts if grid size is very large to prevent integer overflows when counting distance.
The two islands are diagonally adjacent and need a bridge of length 1.	BFS should correctly consider the diagonal neighbors and find the shortest path of length 1.