Shortest Bridge - Leetcode Solution

The problem statement of Shortest Bridge is as follows:

Given a binary matrix A, we want to flip all the 0s to 1s and all the 1s to 0s. The only constraint is that the resulting matrix should contain only one island.

An island is defined as a group of connected 1s, where a connection is defined as adjacent cells horizontally or vertically.

We need to find the minimum number of steps to achieve this.

Solution:

The problem statement requires to flip all the 0s to 1s and all the 1s to 0s in the given binary matrix A in such a way that the resulting matrix contains only one island.

In order to solve this problem, we can follow the following approach:

1. Convert all the 1s to 2s in the matrix A.

2. Traverse through the matrix A and use DFS to identify all the connected components. Mark the cells belonging to each component with 3, 4, 5, and so on. We can also store the list of cells belonging to each component.

3. Initialize the bridge length variable to infinity. For each pair of cells across two components C1 and C2, calculate the shortest distance between the two components, and keep updating the bridge length variable with the minimum distance.

4. After calculating the minimum bridge length, return the bridge length.

Let's implement the above approach in Python.

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
        
        def mark_component(A, i, j, k, Q):
            if i < 0 or i == len(A) or j < 0 or j == len(A[0]) or A[i][j] != 1:
                return
            A[i][j] = k
            Q.append((i,j))
            mark_component(A, i+1, j, k, Q)
            mark_component(A, i-1, j, k, Q)
            mark_component(A, i, j+1, k, Q)
            mark_component(A, i, j-1, k, Q)
        
        def get_components(A):
            components = []
            next_label = 2
            for i in range(len(A)):
                for j in range(len(A[0])):
                    if A[i][j] == 1:
                        Q = []
                        mark_component(A, i, j, next_label, Q)
                        components.append((next_label, Q))
                        next_label += 1
            return components
        
        def get_bridge_length(A, C1, C2):
            min_distance = len(A)*len(A[0])
            for i1, j1 in C1:
                for i2, j2 in C2:
                    distance = abs(i1 - i2) + abs(j1 - j2) - 1
                    if distance < min_distance:
                        min_distance = distance
            return min_distance
        
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == 1:
                    mark_component(A, i, j, 2, [])
                    components = get_components(A)
                    n = len(components)
                    bridge_length = len(A)*len(A[0])
                    for i in range(n):
                        for j in range(i+1,n):
                            component1, cells1 = components[i]
                            component2, cells2 = components[j]
                            bridge_length = min(bridge_length, get_bridge_length(A, cells1, cells2))
                    return bridge_length

The code above implements the solution using DFS and calculates the minimum bridge length by comparing distances between the components.

Time Complexity: O(N^4) where N is the size of the matrix.

Space Complexity: O(N^2) where N is the size of the matrix.

1