Shortest Bridge

BFS

Problem

In a given 2D binary array A, there are two islands. (An island is a 4-directionally connected group of 1s not connected to any other 1s.)

Now, we may change 0s to 1s so as to connect the two islands together to form 1 island.

Return the smallest number of 0s that must be flipped. (It is guaranteed that the answer is at least 1.)

Thought Process

• We care about levels here

• We use DFS to find the first isalnd and change the connecting components to -1. Then we used BFS to find the other island

Solution

from collections import deque

class Solution:
    def shortestBridge(self, A: List[List[int]]) -> int:
    
        q = deque()
        foundOne = False
        
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == 1:
                    print("here", i,j)
                    foundOne = True
                    self.dfs(i, j, A)
                    break
            if foundOne == True:
                break
    
        
        for i in range(len(A)):
            for j in range(len(A[0])):
                if A[i][j] == -1:
                    q.append([i,j])
            
                
        directions = [[-1,0], [1,0], [0,-1], [0,1]]
        level = 0
        
        while q:
            
            levelSize = len(q)
            for _ in range(levelSize):
                coor = q.popleft()
                x = coor[0]
                y = coor[1]
                for d in directions:
                    newX = x+d[0]
                    newY = y+d[1]
                    
                    if newX < 0 or newX >= len(A) or newY < 0 or newY >= len(A[0]) or A[newX][newY] == -1:
                        continue
                    
                    elif A[newX][newY] == 0:
                        A[newX][newY] = -1
                        q.append([newX, newY])
                        
                    elif A[newX][newY] == 1:
                        return level 
            level+=1
                    
        return level   
                
    
    def dfs(self, i, j, A):
        if i < 0 or i >= len(A) or j < 0 or j >= len(A[0]) or A[i][j] == 0 or A[i][j] == -1:
            return 

        A[i][j] = -1
        self.dfs(i-1, j, A)
        self.dfs(i+1, j, A)
        self.dfs(i, j-1, A)
        self.dfs(i, j+1, A)
        

Time Complexity

• Time: O(n^2) because it depends on the DFS. If we have all 1's then the time will be O(n^2)

• Space: O(n^2) for the recursion stack of DFS