Solve diameter and shortest bridge problems

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/

Shortest Bridge Between Two Islands

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

Examples

Example 1

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

Explanation: Flip one 0 (either grid[0][0] or grid[1][1]) to connect the two islands.

Example 2

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

Explanation: Flip two zeros along the shortest path to connect the islands.

Hints

1. Use DFS to find and mark all cells of the first island.
2. Start a multi-source BFS from all marked cells to expand over water.
3. The first time BFS reaches a land cell not marked as the first island, return the current distance.

Approach

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)