934. Shortest Bridge LeetCode Solution

In this guide, you will get 934. Shortest Bridge LeetCode Solution with the best time and space complexity. The solution to Shortest Bridge problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Shortest Bridge solution in C++
Shortest Bridge solution in Java
Shortest Bridge solution in Python
Additional Resources

934. Shortest Bridge LeetCode Solution image

Problem Statement of 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.

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.

Complexity Analysis

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

934. Shortest Bridge LeetCode Solution in C++

class Solution {
 public:
  int shortestBridge(vector<vector<int>>& grid) {
    markGridTwo(grid);

    for (int color = 2;; ++color)
      for (int i = 0; i < grid.size(); ++i)
        for (int j = 0; j < grid[0].size(); ++j)
          if (grid[i][j] == color)
            if (expand(grid, i + 1, j, color) ||  //
                expand(grid, i - 1, j, color) ||  //
                expand(grid, i, j + 1, color) ||  //
                expand(grid, i, j - 1, color))
              return color - 2;
  }

 private:
  // Marks one group to 2s by DFS.
  void markGridTwo(vector<vector<int>>& grid) {
    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] == 1) {
          markGridTwo(grid, i, j);
          return;
        }
  }

  void markGridTwo(vector<vector<int>>& grid, int i, int j) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return;
    if (grid[i][j] != 1)
      return;
    grid[i][j] = 2;
    markGridTwo(grid, i + 1, j);
    markGridTwo(grid, i - 1, j);
    markGridTwo(grid, i, j + 1);
    markGridTwo(grid, i, j - 1);
  }

  // Returns true if we touch 1s' group through expanding.
  bool expand(vector<vector<int>>& grid, int i, int j, int color) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return false;
    if (grid[i][j] == 0)
      grid[i][j] = color + 1;
    return grid[i][j] == 1;
  }
};
/* code provided by PROGIEZ */

934. Shortest Bridge LeetCode Solution in Java

class Solution {
  public int shortestBridge(int[][] grid) {
    markGridTwo(grid);

    for (int color = 2;; ++color)
      for (int i = 0; i < grid.length; ++i)
        for (int j = 0; j < grid[0].length; ++j)
          if (grid[i][j] == color)
            if (expand(grid, i + 1, j, color) || expand(grid, i - 1, j, color) ||
                expand(grid, i, j + 1, color) || expand(grid, i, j - 1, color))
              return color - 2;
  }

  // Marks one group to 2s by DFS.
  private void markGridTwo(int[][] grid) {
    for (int i = 0; i < grid.length; ++i)
      for (int j = 0; j < grid[0].length; ++j)
        if (grid[i][j] == 1) {
          markGridTwo(grid, i, j);
          return;
        }
  }

  private void markGridTwo(int[][] grid, int i, int j) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return;
    if (grid[i][j] != 1)
      return;
    grid[i][j] = 2;
    markGridTwo(grid, i + 1, j);
    markGridTwo(grid, i - 1, j);
    markGridTwo(grid, i, j + 1);
    markGridTwo(grid, i, j - 1);
  }

  // Returns true if we touch 1s' group through expanding.
  private boolean expand(int[][] grid, int i, int j, int color) {
    if (i < 0 || i == grid.length || j < 0 || j == grid[0].length)
      return false;
    if (grid[i][j] == 0)
      grid[i][j] = color + 1;
    return grid[i][j] == 1;
  }
}
// code provided by PROGIEZ

934. Shortest Bridge LeetCode Solution in Python

class Solution {
 public:
  int shortestBridge(vector<vector<int>>& grid) {
    constexpr int dirs[4][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    const int n = grid.size();
    queue<pair<int, int>> q;

    markGridTwo(grid, q);

    for (int ans = 0; !q.empty(); ++ans)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [i, j] = q.front();
        q.pop();
        for (const auto& [dx, dy] : dirs) {
          const int x = i + dx;
          const int y = j + dy;
          if (x < 0 || x == n || y < 0 || y == n)
            continue;
          if (grid[x][y] == 2)
            continue;
          if (grid[x][y] == 1)
            return ans;
          grid[x][y] = 2;
          q.emplace(x, y);
        }
      }

    throw;
  }

 private:
  // Marks one group to 2s by DFS.
  void markGridTwo(vector<vector<int>>& grid, queue<pair<int, int>>& q) {
    for (int i = 0; i < grid.size(); ++i)
      for (int j = 0; j < grid[0].size(); ++j)
        if (grid[i][j] == 1) {
          markGridTwo(grid, i, j, q);
          return;
        }
  }

  // Marks one group to 2s by DFS and pushes them to the queue.
  void markGridTwo(vector<vector<int>>& grid, int i, int j,
                   queue<pair<int, int>>& q) {
    if (i < 0 || i == grid.size() || j < 0 || j == grid[0].size())
      return;
    if (grid[i][j] != 1)
      return;
    grid[i][j] = 2;
    q.emplace(i, j);
    markGridTwo(grid, i + 1, j, q);
    markGridTwo(grid, i - 1, j, q);
    markGridTwo(grid, i, j + 1, q);
    markGridTwo(grid, i, j - 1, q);
  }
};
 # code by PROGIEZ