bugl
bugl
HomeLearnPatternsPathsSearchPremium
HomeLearnPatternsPaths
MediumGraphsLC 934

Shortest Bridge

You are given an n x n binary matrix grid where 1 represents land and 0 represents water. An island is a 4-directionally connected group of 1's not connected to any other 1's. There are exactly two islands in grid. You may change 0's to 1's to connect the two islands to form one island. Return the smallest number of 0's you must flip to connect the two islands.

Asked at 5 companies
FacebookGoogleMckinsey
Hints
  • 1.Think about which data structure fits best
  • 2.Consider the time complexity of your approach
  • 3.Look for patterns in the constraints
LeetCode