Shortest bridge

Array Depth-First Search Breadth-First Search Matrix

59.3% acceptance

Feb 25, 2026

5767

220

You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid. You may change 0's to 1's to connect the two islands to form one island. Return the smallest number of 0's you must flip to connect the two islands.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn shortest_bridge(mut grid: Vec<Vec<i32>>) -> i32 {
    let n = grid.len();
    let dirs = [(0i32,1i32),(0,-1),(1,0),(-1,0)];
    // Find first island via DFS, mark as 2
    let mut stack = Vec::new();
     'outer: for i in 0..n {
      for j in 0..n {
        if grid[i][j] == 1 {
          // DFS to mark entire island as 2
          let mut dfs = vec![(i, j)];
          grid[i][j] = 2;
          while let Some((r, c)) = dfs.pop() {
            stack.push((r, c, 0i32));
            for &(dr, dc) in &dirs {
              let nr = r as i32 + dr;
              let nc = c as i32 + dc;
              if nr >= 0 && nr < n as i32 && nc >= 0 && nc < n as i32 {
                let (nr, nc) = (nr as usize, nc as usize);
                if grid[nr][nc] == 1 {
                  grid[nr][nc] = 2;
                  dfs.push((nr, nc));
                }
              }
            }
          }
          break 'outer;
        }
      }
    }
    // BFS from island 1 (marked 2) to find island 2 (marked 1)
    let mut queue = std::collections::VecDeque::from(stack.into_iter().map(|(r,c,_)| (r,c,0)).collect::<Vec<_>>());
    while let Some((r, c, dist)) = queue.pop_front() {
      for &(dr, dc) in &dirs {
        let nr = r as i32 + dr;
        let nc = c as i32 + dc;
        if nr >= 0 && nr < n as i32 && nc >= 0 && nc < n as i32 {
          let (nr, nc) = (nr as usize, nc as usize);
          if grid[nr][nc] == 1 { return dist; }
          if grid[nr][nc] == 0 {
            grid[nr][nc] = 2;
            queue.push_back((nr, nc, dist + 1));
          }
        }
      }
    }
    0
  }
}