Introduction

In this blog post, we will explore how to solve the LeetCode problem "934" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

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: 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].length 2 <= n <= 100 grid[i][j] is either 0 or 1. There are exactly two islands in grid.

Explanation

Here's a breakdown of the approach and the Python code:

• Identify an Island: Use Depth-First Search (DFS) to find one of the islands. Mark all cells belonging to this island with a distinct value (e.g., 2) to differentiate it from the rest of the grid.

• Breadth-First Search (BFS) Expansion: Start a BFS from the cells of the identified island. Expand outwards, layer by layer, counting the number of 0's flipped (i.e., the distance) until you encounter a cell belonging to the other island (marked as 1).

• Return Minimum Distance: The number of 0's flipped to connect the islands is the shortest path, which is the number of BFS steps taken minus 1 (since we start from the island itself).

• Runtime Complexity: O(N*N), where N is the size of the grid.

• Storage Complexity: O(N*N) in the worst case (queue can contain all cells).

Code

    from collections import deque

def shortestBridge(grid):
    n = len(grid)

    def dfs(i, j, island_id):
        if i < 0 or i >= n or j < 0 or j >= n or grid[i][j] != 1:
            return
        grid[i][j] = island_id
        dfs(i + 1, j, island_id)
        dfs(i - 1, j, island_id)
        dfs(i, j + 1, island_id)
        dfs(i, j - 1, island_id)

    # Find the first island and mark it as 2
    island_found = False
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 1:
                dfs(i, j, 2)
                island_found = True
                break
        if island_found:
            break

    # BFS to find the shortest bridge
    queue = deque()
    for i in range(n):
        for j in range(n):
            if grid[i][j] == 2:
                queue.append((i, j, 0))  # (row, col, distance)

    while queue:
        row, col, distance = queue.popleft()

        for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
            new_row, new_col = row + dr, col + dc

            if 0 <= new_row < n and 0 <= new_col < n:
                if grid[new_row][new_col] == 1:
                    return distance
                elif grid[new_row][new_col] == 0:
                    grid[new_row][new_col] = 2  # Mark as visited
                    queue.append((new_row, new_col, distance + 1))

    return -1  # Should not happen, as there are always two islands