Shortest Bridge
Updated
Problem statement
You are given an n x n grid where 1 is land and 0 is water. An island is a group of land cells joined through shared sides (up, down, left or right; cells that touch only at a corner are not joined). The grid contains exactly two islands.
You may turn water cells into land. Return the smallest number of water cells you must turn into land so that the two islands become one island.
Function
shortestBridge(grid: int[][]) → intExamples
Example 1
grid = [[0,1,0],[0,0,0],[0,0,1]]return = 2The two islands are the single cells (0, 1) and (2, 2) (row, column, 0-based). Turning (1, 1) and (1, 2) into land joins them along (0, 1), (1, 1), (1, 2), (2, 2). One flip is not enough, because no water cell touches both islands. The answer is 2.
Example 2
grid = [[1,1,1,1,1],[1,0,0,0,1],[1,0,1,0,1],[1,0,0,0,1],[1,1,1,1,1]]return = 1The outer ring is one island and the center cell (2, 2) is the other. The water cell (1, 2) touches both, so one flip is enough.
Example 3
grid = [[1,0],[0,1]]return = 1The two land cells touch only at a corner, so they are two separate islands. Turning (0, 1) into land joins them: the answer is 1.
Constraints
n == grid.length == grid[i].lengthand2 <= n <= 20- Every
grid[i][j]is0or1. - There are exactly two islands.
More Microsoft Onsite Interview questions
- Longest Substring Without Repeating CharactersONSITE INTERVIEW · Seen Nov 2026
- Valid ParenthesesONSITE INTERVIEW · Seen Nov 2026
- Count a User's Actions in an Event LogONSITE INTERVIEW · Seen Nov 2026
- Smallest Batch Size Within a Step LimitONSITE INTERVIEW · Seen Nov 2026
- Count Subarrays with Equal Even and Odd CountsONSITE INTERVIEW · Seen Nov 2026
- Minimum Time to Rot All OrangesONSITE INTERVIEW · Seen Nov 2026
- Coin ChangeONSITE INTERVIEW · Seen Oct 2026
- Daily USD Totals with Effective-Dated Exchange RatesONSITE INTERVIEW · Seen Oct 2026
- Number Words to Digits in Any LanguageONSITE INTERVIEW · Seen Oct 2026
- Totals from a Tiered Rate TableONSITE INTERVIEW · Seen Oct 2026
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- Shortest Bridge Between Two IslandsCompass International Holdings · ONSITE INTERVIEWCompass International Holdings interview questions
- Number of Islands with Diagonal ConnectivityGoogle · ONSITE INTERVIEWGoogle interview questions
- Island Count and Maximum AreaOracle · ONSITE INTERVIEWOracle interview questions
- Number of Closed IslandsSnap Inc. · ONSITE INTERVIEWSnap Inc. interview questions
- The MazeGoldman Sachs · ONSITE INTERVIEWGoldman Sachs interview questions
- Mouse and Cheese ReachabilityMeta · ONSITE INTERVIEWMeta interview questions
- Number of IslandsTripjack · ONSITE INTERVIEWTripjack interview questions
- Number of IslandsTekion · ONSITE INTERVIEWTekion interview questions
- Grid Pathfinding with Obstacles (DFS)Roblox · PHONE SCREEN · ONSITE INTERVIEWRoblox interview questions