# Shortest Bridge

## Problem

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

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

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

![](https://1063826111-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-MGdx41c9p2PMgIHbUTK%2F-MRLb8CxHJIReYjpYwLF%2F-MRLcvP0na9LMlnbqbrr%2FScreen%20Shot%202021-01-18%20at%2010.55.58%20AM.png?alt=media\&token=28582df9-f471-430c-a328-ba50af0a95c9)

### 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