Shortest Bridge Between Two Islands
Updated
Problem statement
You are given an n x n grid grid in which 1 is land and 0 is water. An island is a group of land cells connected through shared sides: up, down, left, or right. Cells that touch only at a corner are not connected. The grid contains exactly two islands.
You may change water cells into land. Return the smallest number of water cells you must change so that the two islands become a single island.
Function
shortestBridge(grid: int[][]) → intExamples
Example 1
grid = [[1,1,0],[0,0,0],[0,0,1]]return = 2The first island is (0, 0) and (0, 1) (row, column, 0-based); the second island is (2, 2). Turning (1, 1) and (1, 2) into land gives the side-connected path (0, 1), (1, 1), (1, 2), (2, 2), so 2 flips are enough. One flip is not: no water cell shares a side with both islands. The answer is 2.
Example 2
grid = [[1,0,0],[0,1,0],[0,0,0]]return = 1The cells (0, 0) and (1, 1) touch only at a corner, so they are two separate islands. The water cell (0, 1) shares a side with both, so turning it into land joins them. The answer is 1.
Example 3
grid = [[1,1,1,1],[0,0,0,1],[0,1,0,1],[0,0,0,0]]return = 1The first island is the top row plus (1, 3) and (2, 3); the second island is the single cell (2, 1). The water cell (1, 1) touches (0, 1) above it and (2, 1) below it, so one flip joins the islands. The answer is 1.
Constraints
n == grid.length == grid[i].length2 <= n <= 100- Every
grid[i][j]is0or1. - The grid contains exactly two islands.
More Compass International Holdings interview questions
- Decode StringPHONE SCREEN · Seen Oct 2026
- Lowest Common Ancestors in a Parent DAGPHONE SCREEN · Seen Apr 2022
- Can One Dictionary Word Supply the Target Letters?PHONE SCREEN · Seen Apr 2022
- Greedy Grid Word Occurrences with No Reused CellsPHONE SCREEN · Seen Apr 2022
- Word Path Moving Only Right or DownPHONE SCREEN · Seen Apr 2022
- First Dictionary Word from Note LettersPHONE SCREEN · Seen Mar 2022
- Word Path Moving Only Up or RightPHONE SCREEN · Seen Feb 2022
- Top Five Stock Records in a Date RangePHONE SCREEN · Seen Oct 2021
- Do Two Nodes Share a Proper Ancestor?OA · Seen Jul 2021
- Nodes With Zero or One ParentOA · Seen Jul 2021
Similar questions at other companies
- Number of IslandsAmazon · PHONE SCREEN · ONSITE INTERVIEW
- 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
- Foreground Region SizesMicrosoft · ONSITE INTERVIEWMicrosoft 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