> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# Shortest Bridge Python Solution with Tests

> Tested Python solution for LeetCode 934 with 13 pytest cases. Generate a practice environment with lcpy.

LeetCode 934, [Medium](/catalog/medium). Topics: [Array](/catalog/topics/array), [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Matrix](/catalog/topics/matrix). [View on LeetCode](https://leetcode.com/problems/shortest-bridge/description/).

Generate this problem as a practice environment: tested reference solution, 13 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 934   # by problem number
lcpy gen -s shortest_bridge   # by problem name
```

## Problem

\<p>You are given an \<code>n x n\</code> binary matrix \<code>grid\</code> where \<code>1\</code> represents land and \<code>0\</code> represents water.\</p>

\<p>An island is a 4-directionally connected group of \<code>1\</code>'s not connected to any other \<code>1\</code>'s. There are \<strong>exactly two islands\</strong> in \<code>grid\</code>.\</p>

\<p>You may change \<code>0\</code>'s to \<code>1\</code>'s to connect the two islands to form \<strong>one island\</strong>.\</p>

\<p>Return \<em>the smallest number of \</em>\<code>0\</code>\<em>'s you must flip to connect the two islands\</em>.\</p>

### Examples

```
Input: grid = [[0,1],[1,0]]
Output: 1
```

```
Input: grid = [[0,1,0],[0,0,0],[0,0,1]]
Output: 2
```

```
Input: grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]
Output: 1
```

### Constraints

* n == grid.length == grid\[i].length
* 2 \<= n \<= 100
* grid\[i]\[j] is either 0 or 1.
* There are exactly two islands in grid.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_bridge/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/shortest_bridge/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
from collections import deque


class Solution:
    # Time: O(n^2)
    # Space: O(n^2)
    def shortest_bridge(self, grid: list[list[int]]) -> int:
        n = len(grid)

        def neighbors(row: int, col: int) -> list[tuple[int, int]]:
            result = []
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = row + dr, col + dc
                if 0 <= nr < n and 0 <= nc < n:
                    result.append((nr, nc))
            return result

        # Find and mark the first island (DFS)
        start = next((r, c) for r in range(n) for c in range(n) if grid[r][c] == 1)
        first_island: deque[tuple[int, int]] = deque()
        stack = [start]
        grid[start[0]][start[1]] = -1
        while stack:
            row, col = stack.pop()
            first_island.append((row, col))
            for nr, nc in neighbors(row, col):
                if grid[nr][nc] == 1:
                    grid[nr][nc] = -1
                    stack.append((nr, nc))

        # Multi-source BFS from the first island until the second is reached
        distance = 0
        while first_island:
            for _ in range(len(first_island)):
                row, col = first_island.popleft()
                for nr, nc in neighbors(row, col):
                    if grid[nr][nc] == 1:
                        return distance
                    if grid[nr][nc] == 0:
                        grid[nr][nc] = -1
                        first_island.append((nr, nc))
            distance += 1
        return -1
```

## Complexity

| Time | Space |
| - | - |
| O(n^2) | O(n^2) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.