FastPrepShortest Bridge Between Two Islands
Problems/Shortest Bridge Between Two Islands

Shortest Bridge Between Two Islands

Compass International Holdings logoCompass International Holdings● MediumFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: In a Compass onsite coding round for a senior software engineering role, the second question was a well-known public problem, named only by its number. It is the shortest bridge between two islands in a grid. The report gives no input format, limits or examples. Our choices: the standard public definition (a square grid of 0s and 1s with exactly two side-connected islands, returning the fewest water cells to turn into land), side adjacency only, a grid size from 2 to 100, and our own examples.

Our version is about 90% the same as the reported question.

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[][]) → int

Examples

Example 1

grid = [[1,1,0],[0,0,0],[0,0,1]]return = 2
grid
012011010002001

The 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 = 1
grid
012010010102000

The 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 = 1
grid
012301111100012010130000

The 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].length
  • 2 <= n <= 100
  • Every grid[i][j] is 0 or 1.
  • 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
All Compass International Holdings interview questionsSee Compass International Holdings hiring insights
Saved
class Solution {
    public int shortestBridge(int[][] grid) {
        // Write your code here.
    }
}
Checking account…