Solution
Approach 1: Find and Grow
Intuition
Conceptually, our method is very straightforward: find both islands, then for one of the islands, keep "growing" it by 1 until we touch the second island.
We can use a depthfirst search to find the islands, and a breadthfirst search to "grow" one of them. This leads to a verbose but correct solution.
Algorithm
To find both islands, look for a square with a 1
we haven't visited, and dfs to get the component of that region. Do this twice. After, we have two components source
and target
.
To find the shortest bridge, do a BFS from the nodes source
. When we reach any node in target
, we will have found the shortest distance.
Please see the code for more implementation details.
Complexity Analysis

Time Complexity: , where is the content of
A
. 
Space Complexity: .
Analysis written by: @awice.