How do you solve Shortest Bridge on LeetCode?

Shortest Bridge (LeetCode #934) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n²) time complexity and O(n) space complexity. Key insight: Using BFS from both islands minimizes the number of flips needed.

What is the brute force solution for Shortest Bridge?

The brute force approach for Shortest Bridge is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking every possible path from one island to the other and counting the number of 0's that need to be flipped. This method is straightforward but inefficient, as it explores all potential connections. The optimal Optimal Solution approach improves this to O(n²).

What algorithm or data structure is used to solve Shortest Bridge?

Shortest Bridge uses the following concepts: Array, Depth-First Search, Breadth-First Search, Matrix. The recommended patterns to study are: Depth-First Search, Breadth-First Search, Graph Traversal.

What are the interview tips for Shortest Bridge?

Explain your thought process clearly while coding. Consider edge cases and test your solution with them. Practice writing clean and efficient code.

What are common mistakes when solving Shortest Bridge?

Not marking visited cells properly can lead to infinite loops. Failing to account for edge cases like islands being adjacent.

#934

Shortest Bridge

Medium

ArrayDepth-First SearchBreadth-First SearchMatrixDepth-First SearchBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n²)
Space	O(1)	O(n)

💡

Intuition

Time O(n²)Space O(n)

The optimal solution leverages a multi-source BFS starting from both islands simultaneously. This allows us to efficiently find the shortest path between the two islands by expanding outwards, minimizing the number of flips needed.

⚙️

Algorithm

3 steps

1Step 1: Use DFS to identify the first island and mark its cells.
2Step 2: Initialize a queue with all cells of the first island and perform BFS to explore neighboring cells.
3Step 3: For each cell in the BFS, if a cell from the second island is reached, return the distance as the minimum flips needed.

solution.py38 lines

1def shortestBridge(grid):
2    n = len(grid)
3    visited = [[False] * n for _ in range(n)]
4
5    def dfs(x, y):
6        if x < 0 or x >= n or y < 0 or y >= n or visited[x][y] or grid[x][y] == 0:
7            return
8        visited[x][y] = True
9        island.append((x, y))
10        dfs(x + 1, y)
11        dfs(x - 1, y)
12        dfs(x, y + 1)
13        dfs(x, y - 1)
14
15    island = []
16    for i in range(n):
17        for j in range(n):
18            if grid[i][j] == 1 and not visited[i][j]:
19                dfs(i, j)
20                break
21        if island:
22            break
23
24    queue = collections.deque(island)
25    distance = 0
26    while queue:
27        for _ in range(len(queue)):
28            x, y = queue.popleft()
29            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
30                nx, ny = x + dx, y + dy
31                if 0 <= nx < n and 0 <= ny < n:
32                    if grid[nx][ny] == 1:
33                        return distance
34                    if not visited[nx][ny]:
35                        visited[nx][ny] = True
36                        queue.append((nx, ny))
37        distance += 1
38    return -1

ℹ

Complexity note: The time complexity is still O(n²) due to the need to explore the grid, but the space complexity is O(n) because we store the cells of the first island and the BFS queue.

1Using BFS from both islands minimizes the number of flips needed.
2Identifying islands with DFS is crucial for the solution.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.