Find shortest distance between two islands
Company: Coupang
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
You are given an `R x C` binary grid where:
- `1` represents land
- `0` represents water
The grid contains **exactly two** 4-directionally connected islands (connected via up/down/left/right). You may flip water cells (`0`) into land (`1`).
Return the **minimum number of water cells to flip** so that the two islands become connected (i.e., there exists a 4-directional path of `1`s between them).
### Input
- `grid`: 2D array of integers (`0` or `1`)
### Output
- An integer: the minimum number of flips needed.
### Constraints (reasonable interview assumptions)
- `1 <= R, C <= 200`
- Exactly two islands exist.
### Example
If flipping a single `0` cell can connect the islands, return `1`.
Quick Answer: This question evaluates understanding of grid-graph traversal and shortest-path concepts, including identification of connected components and reasoning about minimal bridging distance between regions.
You are given an R x C binary grid where 1 represents land and 0 represents water. The grid contains exactly two distinct islands, and each island is formed by 4-directionally connected land cells (up, down, left, right). You may flip water cells from 0 to 1. Return the minimum number of water cells that must be flipped so the two islands become connected.
Constraints
- 1 <= R, C <= 200
- grid[i][j] is either 0 or 1
- There are exactly two islands in the grid
- Cells are connected only in 4 directions: up, down, left, and right
Examples
Input: ([[0, 1], [1, 0]])
Expected Output: 1
Explanation: The two islands are diagonally adjacent. Flipping either (0,0) or (1,1) connects them.
Input: ([[0, 1, 0], [0, 0, 0], [0, 0, 1]])
Expected Output: 2
Explanation: A shortest connection flips two water cells, such as (1,1) and (1,2).
Hints
- First, find one of the islands and mark all of its cells.
- Then run a multi-source BFS starting from every cell of that island at once. The first time you reach the other island gives the minimum number of flips.