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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Shortest Bridge

Difficulty: Medium

Problem Description

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.

Key Insights

  • We need to identify the two separate islands in the grid.
  • We can perform a Breadth-First Search (BFS) or Depth-First Search (DFS) to find the islands and their boundary cells.
  • The goal is to find the shortest distance (in terms of 0's) between the two islands.
  • The problem can be visualized as a search for the shortest path in an unweighted graph, where the nodes are the 0's connecting the two islands.

Space and Time Complexity

Time Complexity: O(n^2) - We may need to scan the entire grid to identify the islands and their boundaries.
Space Complexity: O(n^2) - Used for storing the distance of boundary cells and the queue for BFS/DFS.

Solution

To solve the problem, we can use a combination of BFS/DFS to identify the two islands and then calculate the minimum number of flips needed to connect them:

  1. Use DFS to mark one of the islands and store its boundary cells.
  2. Perform BFS from the boundary cells of the first island, expanding outward to find the nearest boundary cell of the second island.
  3. Count the number of 0's encountered during the BFS until we reach the second island, which will give us the required number of flips.

Code Solutions

def shortestBridge(grid):
    n = len(grid)

    def dfs(x, y, boundary):
        # Mark the cell as visited by setting it to 2
        grid[x][y] = 2
        # Check all 4 directions
        for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < n:
                if grid[nx][ny] == 1:
                    dfs(nx, ny, boundary)
                elif grid[nx][ny] == 0:
                    boundary.append((nx, ny))

    # Step 1: Find the first island and its boundary
    boundary = []
    found = False
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j, boundary)
                found = True
                break
        if found:
            break

    # Step 2: Use BFS from the boundary to find the shortest distance to the second island
    queue = collections.deque(boundary)
    distance = 0
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n:
                    if grid[nx][ny] == 1:
                        return distance  # Found the second island
                    if grid[nx][ny] == 0:
                        grid[nx][ny] = 2  # Mark as visited
                        queue.append((nx, ny))
        distance += 1

    return -1  # Should never reach here since there are exactly two islands
← Back to All Questions