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.
Example 1:
Input: grid = [[0,1],[1,0]] Output: 1
Example 2:
Input: grid = [[0,1,0],[0,0,0],[0,0,1]] Output: 2
Example 3:
Input: 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]] Output: 1
Constraints:
n == grid.length == grid[i].length2 <= n <= 100grid[i][j] is either 0 or 1.grid.This approach involves two primary steps:
1. Use DFS to mark one of the islands completely.
2. Use BFS from the boundary of that marked island to find the shortest path to the other island.
The BFS will expand layer by layer, counting the zeros flipped until the boundary of the second island is reached.
This solution first uses DFS to mark all the cells of the first island. Each cell belonging to the island is added to a queue.
By using DFS for marking, we ensure all island cells are explored. Once marked, a BFS is used to expand outwards from all boundary points simultaneously, effectively finding the shortest path to the second island.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N^2), where N is the size of the grid, because each cell is processed at most twice (once in DFS and once in BFS).
Space Complexity: O(N^2), for the visited array and the queue holding grid indices.
Shortest Bridge - Leetcode 934 - Python • NeetCode • 42,489 views views
Watch 9 more video solutions →Practice Shortest Bridge with our built-in code editor and test cases.
Practice on FleetCode