Solve diameter and shortest bridge problems
Company: Meta
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Technical Screen
##### Question
LeetCode 543. Diameter of Binary Tree LeetCode 934. Shortest Bridge
https://leetcode.com/problems/diameter-of-binary-tree/description/ https://leetcode.com/problems/shortest-bridge/description/
Quick Answer: This question evaluates proficiency with tree and graph data structures and traversal techniques, focusing on computing binary tree metrics and shortest-path distances in grid-based graphs.
You are given an n x n binary grid where 0 represents water and 1 represents land. The grid contains exactly two islands, where an island is a group of 1s connected 4-directionally (up, down, left, right). Return the minimum number of 0s that must be flipped to 1 to connect the two islands (i.e., the length of the shortest bridge).
Constraints
- 2 <= n <= 200
- grid is an n x n matrix of 0s and 1s
- grid contains exactly two islands
- Islands are connected 4-directionally
- Answer fits in a 32-bit integer
Solution
from typing import List
from collections import deque
def shortest_bridge(grid: List[List[int]]) -> int:
n = len(grid)
directions = [(1,0), (-1,0), (0,1), (0,-1)]
visited = [[False]*n for _ in range(n)]
q = deque()
def in_bounds(r: int, c: int) -> bool:
return 0 <= r < n and 0 <= c < n
def dfs_mark_island(r: int, c: int) -> None:
if not in_bounds(r, c) or visited[r][c] or grid[r][c] == 0:
return
visited[r][c] = True
q.append((r, c, 0)) # seed BFS with all first-island cells
for dr, dc in directions:
dfs_mark_island(r + dr, c + dc)
# 1) Find and mark the first island
found = False
for i in range(n):
if found:
break
for j in range(n):
if grid[i][j] == 1:
dfs_mark_island(i, j)
found = True
break
# 2) BFS to reach the second island
while q:
r, c, d = q.popleft()
for dr, dc in directions:
nr, nc = r + dr, c + dc
if in_bounds(nr, nc) and not visited[nr][nc]:
if grid[nr][nc] == 1:
return d # reached second island
visited[nr][nc] = True
q.append((nr, nc, d + 1))
return -1 # should not happen if exactly two islands existExplanation
Mark one island using DFS and push all its cells into a queue. Then perform a multi-source BFS expanding over water cells (zeros), increasing distance layer by layer. When BFS first encounters an unvisited land cell, it belongs to the second island; the current distance equals the minimum number of zero flips required to connect the islands.
Time complexity: O(n^2). Space complexity: O(n^2).
Hints
- Use DFS to find and mark all cells of the first island.
- Start a multi-source BFS from all marked cells to expand over water.
- The first time BFS reaches a land cell not marked as the first island, return the current distance.