Find shortest distance between two islands

Q: Find shortest distance between two islands

This is a Coding & Algorithms interview question from Coupang for Software Engineer roles. View the full question and solution on PracHub.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.