What is the time complexity of Shortest Bridge?

The optimal solution has a time complexity of O(n^2).

What data structures are used to solve Shortest Bridge?

This problem uses Array, Depth-First Search, Breadth-First Search, Matrix. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Shortest Bridge?

Insight 1: Identify one island using Depth-First Search (DFS) or Breadth-First Search (BFS) and mark all its cells. Insight 2: Use BFS to expand from the identified island, layer by layer, until the second island is reached. The number of layers traversed represents the shortest bridge length.

Which companies ask LeetCode 934. Shortest Bridge in interviews?

This problem is frequently asked at Coupang, Docusign, Flipkart, McKinsey, Snap.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Shortest Bridge - LeetCode 934 Solution

Q: What is the space complexity of Shortest Bridge?

The space complexity is O(n^2).

Shortest Bridge - Complete Solution Guide

Shortest Bridge is LeetCode problem 934, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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:

Detailed Explanation

The problem asks us to find the shortest 'bridge' between two islands in a binary matrix (grid). The grid contains 0s (water) and 1s (land). An island is a group of 4-directionally connected 1s. The goal is to change the minimum number of 0s to 1s to connect the two islands into a single island. The input is an n x n grid of 0s and 1s, with the constraint that there are exactly two separate islands. The output is the minimum number of 0s that need to be flipped to connect the islands.

Solution Approach

The provided solution uses a combination of Depth-First Search (DFS) and Breadth-First Search (BFS). First, DFS is used to find one of the islands and mark it (by changing the '1' values to '2'). Then, BFS is used to find the shortest path from this marked island to the other island. Each level of BFS represents an increment of distance, essentially expanding outward from the first island until the other island is encountered.

Step-by-Step Algorithm

Step 1: Iterate through the grid to find the first '1' (land) cell. This signifies the start of the first island.
Step 2: Use DFS (or BFS) to explore the first island and mark all its cells as '2'. During the DFS/BFS, add these cells to a queue. The queue will be used for the next BFS step.
Step 3: Initialize a 'distance' variable to 0. This represents the number of '0' cells we need to flip.
Step 4: Perform BFS starting from the queue (containing the cells of the first island).
Step 5: In each BFS level, iterate through all cells in the queue.
Step 6: For each cell, explore its 4-directional neighbors.
Step 7: If a neighbor is '1' (part of the second island), return the current 'distance'.
Step 8: If a neighbor is '0' (water), change it to '2' (visited) and add it to the queue. This expands the search outwards from the first island.
Step 9: Increment the 'distance' after each BFS level. This represents the number of '0' cells crossed.
Step 10: If the BFS completes without finding the second island, return -1 (although this should not happen given the problem constraints).

Key Insights

Insight 1: Identify one island using Depth-First Search (DFS) or Breadth-First Search (BFS) and mark all its cells.
Insight 2: Use BFS to expand from the identified island, layer by layer, until the second island is reached. The number of layers traversed represents the shortest bridge length.
Insight 3: The problem can be solved by first marking one of the islands and then finding the shortest path (in terms of 0s crossed) to the other island, using the first island as the starting point.

Complexity Analysis

Time Complexity: O(n^2)

Space Complexity: O(n^2)

Topics

This problem involves: Array, Depth-First Search, Breadth-First Search, Matrix.

Companies

Asked at: Coupang, Docusign, Flipkart, McKinsey, Snap.

Shortest Bridge | LeetCode 934

Medium

Array Depth-First Search Breadth-First Search Matrix

Time: O(n^2)Space: O(n^2)

Solution Code

Available in:

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int shortestBridge(int[][] grid) {
        int n = grid.length;
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
        Deque<int[]> q = new ArrayDeque<>();

        boolean found = false;
        for (int r = 0; r < n; r++) {
            if (found) {
                break;
            }
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == 1) {
                    Deque<int[]> island_q = new ArrayDeque<>();
                    island_q.add(new int[]{r, c});
                    grid[r][c] = 2;
                    q.add(new int[]{r, c});
                    while (!island_q.isEmpty()) {
                        int[] curr = island_q.poll();
                        int curr_r = curr[0];
                        int curr_c = curr[1];
                        for (int[] dir : directions) {
                            int dr = dir[0];
                            int dc = dir[1];
                            int nr = curr_r + dr;
                            int nc = curr_c + dc;
                            if (0 <= nr && nr < n && 0 <= nc && nc < n && grid[nr][nc] == 1) {
                                grid[nr][nc] = 2;
                                q.add(new int[]{nr, nc});
                                island_q.add(new int[]{nr, nc});
                            }
                        }
                    }
                    found = true;
                    break;
                }
            }
        }

        int distance = 0;
        while (!q.isEmpty()) {
            int level_size = q.size();
            for (int i = 0; i < level_size; i++) {
                int[] curr = q.poll();
                int r = curr[0];
                int c = curr[1];
                for (int[] dir : directions) {
                    int dr = dir[0];
                    int dc = dir[1];
                    int nr = r + dr;
                    int nc = c + dc;
                    if (0 <= nr && nr < n && 0 <= nc && nc < n) {
                        if (grid[nr][nc] == 1) {
                            return distance;
                        } else if (grid[nr][nc] == 0) {
                            grid[nr][nc] = 2;
                            q.add(new int[]{nr, nc});
                        }
                    }
                }
            }
            distance += 1;
        }

        return -1;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 934: Shortest Bridge - Detailed explanation and solution approaches.

Topics

Array Depth-First Search Breadth-First Search Matrix

Companies

CoupangDocusignFlipkartMcKinseySnap

Stats

Difficulty:Medium

Languages:4

Companies:5

Problem #:934

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

10 steps

1
Step 1: Iterate through the grid to find the first '1' (land) cell. This signifies the start of the first island.
2
Step 2: Use DFS (or BFS) to explore the first island and mark all its cells as '2'. During the DFS/BFS, add these cells to a queue. The queue will be used for the next BFS step.
3
Step 3: Initialize a 'distance' variable to 0. This represents the number of '0' cells we need to flip.
4
Step 4: Perform BFS starting from the queue (containing the cells of the first island).
5
Step 5: In each BFS level, iterate through all cells in the queue.
6
Step 6: For each cell, explore its 4-directional neighbors.
7
Step 7: If a neighbor is '1' (part of the second island), return the current 'distance'.
8
Step 8: If a neighbor is '0' (water), change it to '2' (visited) and add it to the queue. This expands the search outwards from the first island.
9
Step 9: Increment the 'distance' after each BFS level. This represents the number of '0' cells crossed.
10
Step 10: If the BFS completes without finding the second island, return -1 (although this should not happen given the problem constraints).

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n^2)

🐢 Quadratic - Gets slow with large inputs. Consider optimization!

💾

Space Complexity

O(n^2)

📚 Quadratic space - Uses lots of memory!

📝

Why?

The time complexity is O(n^2) because in the worst case, we might need to visit every cell in the grid during both the DFS/BFS to find the first island and the BFS to find the shortest bridge. The space complexity is O(n^2) because, in the worst case, the queue used for BFS can contain all the cells of the grid (if the first island is very large or almost the entire grid).

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

A* Search

A* search could be used as an alternative to BFS. A* uses a heuristic function to guide the search, potentially finding the shortest path faster in some cases.

Time: O(n^2) in the worst case, but often faster in practiceSpace: O(n^2)

Trade-offs: A* might be faster if the heuristic is well-chosen, but it adds the complexity of implementing and tuning the heuristic function. BFS is simpler to implement and guaranteed to find the shortest path in an unweighted graph like this.

Iterative Deepening Depth-First Search (IDDFS)

IDDFS can be applied here. For each depth limit, perform DFS and check if the second island is reached within that depth. If not, increase the depth and repeat. This combines memory efficiency of DFS with completeness of BFS.

Time: O(n^2)Space: O(depth), where depth is the shortest path length, which is at most n. Therefore, O(n).

Trade-offs: IDDFS can be more memory efficient for large grids compared to BFS because it uses DFS with limited depth. However, IDDFS explores nodes multiple times, potentially increasing the execution time compared to BFS. It is better in situations where memory is a big constraint.

✨

Key Insights

1Insight 1: Identify one island using Depth-First Search (DFS) or Breadth-First Search (BFS) and mark all its cells.
2Insight 2: Use BFS to expand from the identified island, layer by layer, until the second island is reached. The number of layers traversed represents the shortest bridge length.
3Insight 3: The problem can be solved by first marking one of the islands and then finding the shortest path (in terms of 0s crossed) to the other island, using the first island as the starting point.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Edge Cases

Edge case 1: Islands are adjacent. The solution correctly handles this case because the BFS will immediately find the other island and return a distance of 0.
Edge case 2: Grid contains only 0s and 1s. The initial check ensures that the islands will contain at least one '1' cell, so the DFS will start and mark these land cells accordingly.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to mark the visited cells (changing '0' to '2'). This can lead to infinite loops in the BFS.

✗Common mistake 2: Not handling the case where the islands are already connected (distance = 0).

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Image processing - Finding the shortest path between two objects in an image represented as a grid of pixels.

🏦Real-world scenario 2: Network routing - Finding the shortest number of hops (intermediate nodes) to connect two computers in a network. The network can be represented as a graph (or grid) where nodes are computers and edges represent connections.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

If stuck, try working through a small example by hand. The pattern often reveals itself.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: July 5, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 13

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jul 6

❓

Frequently Asked Questions

What is the most efficient way to solve array problems?

Most array problems can be solved efficiently using techniques like two-pointer approach, sliding window, or hash maps. The key is identifying whether the array is sorted (enabling binary search) or if tracking seen elements (using hash maps) can help achieve O(n) time complexity.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Shortest Bridge"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether depth-first search techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?