We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Shortest Bridge

Number: 971

Difficulty: Medium

Paid? No

Companies: Meta, Uber, TikTok, Amazon, Google, Flipkart, Docusign, Microsoft, Adobe, Snap, Apple, Yahoo, McKinsey

Problem Description

Given an n x n binary matrix where 1 represents land and 0 represents water, there are exactly two separate islands (i.e. groups of 4-directionally connected 1's). The goal is to flip 0's into 1's to connect these two islands with the fewest number of flips possible. You must determine the minimum number of 0’s that need to be flipped to connect the two islands.

Key Insights

  • First identify one of the islands and mark all its cells. This is commonly done using Depth-First Search (DFS) or Breadth-First Search (BFS).
  • Once the first island is identified, use multi-source BFS starting from every cell in that island simultaneously.
  • Expand the BFS level by level until any cell from the second island (cell value 1 that is not marked) is encountered. The BFS level at which you first find the second island equals the minimum number of flips required.

Space and Time Complexity

Time Complexity: O(n^2) – In the worst-case, every cell in the grid may be processed once. Space Complexity: O(n^2) – In the worst-case, the space used by the recursion (DFS) or the BFS queue can hold a large fraction of the grid cells.

Solution

The solution first locates one island by scanning the grid and performing DFS from the first encountered land cell. During DFS, mark every cell of the island (e.g. by changing its value to 2) and add it to a BFS queue. Then, execute a BFS starting from the entire first island simultaneously. In each BFS level, examine all neighboring cells; if a neighboring cell belongs to the second island (i.e., its value is 1), the current BFS level represents the answer. If a neighboring cell is water (0), mark it (so it is not processed again) and add it to the BFS queue. Continue this until the second island is reached. Key data structures used include a queue for multi-source BFS and recursive function calls for DFS traversal.

Code Solutions

Below are the code solutions in Python, JavaScript, C++, and Java with detailed line-by-line comments.

from collections import deque

def shortestBridge(grid):
    n = len(grid)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque()  # Queue for BFS from the first island
    found = False   # Flag to indicate when the first island has been marked

    # DFS to mark all cells of the first island
    def dfs(i, j):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
            return
        grid[i][j] = 2  # Mark cell as part of the first island
        queue.append((i, j))  # Add cell to BFS queue
        for di, dj in directions:
            dfs(i + di, j + dj)

    # Locate the first island and use DFS to mark it
    for i in range(n):
        if found:
            break
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j)
                found = True
                break

    # BFS to expand outwards from the first island to find the second island
    steps = 0
    while queue:
        # Process all nodes in the current BFS level
        for _ in range(len(queue)):
            i, j = queue.popleft()
            for di, dj in directions:
                ni, nj = i + di, j + dj
                if 0 <= ni < n and 0 <= nj < n:
                    if grid[ni][nj] == 1:  # If cell belongs to second island, return current depth (flips)
                        return steps
                    if grid[ni][nj] == 0:  # If water cell, mark it and add to queue
                        grid[ni][nj] = 2
                        queue.append((ni, nj))
        steps += 1

    return -1  # Should never reach here

# Example usage:
grid_example = [[0,1],[1,0]]
print(shortestBridge(grid_example))
← Back to All Questions