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
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.