Katkat
Back

Find shortest distance between two islands

CoupangSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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 1s 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.