Approach 1: Find and Grow
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 depth-first search to find the islands, and a breadth-first search to "grow" one of them. This leads to a verbose but correct solution.
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
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.
Time Complexity: , where is the content of
Space Complexity: .
Analysis written by: @awice.