Approach
Breadth-first search
For Shortest Bridge, the implementation explores reachable states in layers, which is the standard shape for unweighted shortest paths and minimum-step transitions.
- Model each valid configuration as a state and each legal move as an edge.
- Seed the queue with the starting state and mark it immediately.
- Expand each state once, recording distance or reachability for unseen neighbours.
Code notes
- 52 lines of Python from the credited upstream file shortest-bridge.py.
- The implementation visibly relies on sequence storage, ordered lookup, work queue.
- No explicit loop blocks detected.
Complexity
Verify that each state and transition is processed only a bounded number of times; that determines the traversal cost.
Check the problem constraints before deciding whether this complexity will pass.
Use this to learn the idea, then write your own version.
123 4import collections5 6 7class Solution(object):8 def shortestBridge(self, A):9 """10 :type A: List[List[int]]11 :rtype: int12 """13 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]14 15 def get_islands(A):16 islands = []17 done = set()18 for r, row in enumerate(A):19 for c, val in enumerate(row):20 if val == 0 or (r, c) in done:21 continue22 s = [(r, c)]23 lookup = set(s)24 while s:25 node = s.pop()26 for d in directions:27 nei = node[0]+d[0], node[1]+d[1]28 if not (0 <= nei[0] < len(A) and 0 <= nei[1] < len(A[0])) or \29 nei in lookup or A[nei[0]][nei[1]] == 0:30 continue31 s.append(nei)32 lookup.add(nei)33 done |= lookup34 islands.append(lookup)35 if len(islands) == 2:36 break37 return islands38 39 lookup, target = get_islands(A)40 q = collections.deque([(node, 0) for node in lookup])41 while q:42 node, dis = q.popleft()43 if node in target:44 return dis-145 for d in directions:46 nei = node[0]+d[0], node[1]+d[1]47 if not (0 <= nei[0] < len(A) and 0 <= nei[1] < len(A[0])) or \48 nei in lookup:49 continue50 q.append((nei, dis+1))51 lookup.add(nei)52