Quick Overview

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.

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/

Overview: 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

  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.

Loading coding console...

Show the approach

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)