PreviousNext
Coding/Graphs and trees

Shortest bridge

Write codeHard35 min

Your task

You are given an n x n binary grid that contains exactly two islands (a group of 1s connected 4-directionally). You may flip 0s to 1s to connect the two islands. Return the smallest number of 0s you must flip to form a single island connecting them. The grid contains exactly two islands.

Examples

shortest_bridge(grid: list[list[int]]) -> int
Example 1
Inputshortest_bridge([[0, 1], [1, 0]])
Output1