FastPrepShortest Bridge
Problems/Shortest Bridge

Shortest Bridge

Microsoft logoMicrosoft● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a review of a Microsoft software engineering internship. The review lists the Shortest Bridge task by name, tagged as a depth-first search exercise, with no input or rules. The round is not named. The review describes an online test followed by several technical interviews.

Here the grid is n x n with 2 <= n <= 20, 1 for land and 0 for water, and it holds exactly two islands (land cells joined up, down, left or right). You return the smallest number of water cells that must become land to join them. The 20 x 20 limit keeps a recursive flood fill under 400 calls deep.

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

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

Examples

Example 1

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

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

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

The 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].length and 2 <= n <= 20
  • Every grid[i][j] is 0 or 1.
  • 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

Interview reports that mention this question

  • Microsoft SWE Intern, Early 2025: 41 Experiences (Part 5 of 6)
  • Microsoft SWE Intern Interviews: 244 Experiences (Part 1 of 6)

Microsoft interview experiences

  • Microsoft Explore and Student SWE: 12 Experiences (Part 6 of 6)
  • Microsoft SWE Intern, Mid 2025: 42 Experiences (Part 4 of 6)
  • Microsoft SWE Intern, Late 2025: 47 Experiences (Part 3 of 6)
  • Microsoft SWE Intern, Early 2026: 54 Experiences (Part 2 of 6)
All Microsoft interview questionsSee Microsoft hiring insights
Saved
class Solution {
    public int shortestBridge(int[][] grid) {
        // Write your code here.
    }
}
Checking account…