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

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.