← Coupang Interview Insights

Coupang·Software Engineer·Technical Phone Screen·Intermediate

IntermediatePrefer not to say
Jun 2026

Summary

Got a graph problem from Coupang that looks deceptively clean on the surface but has a few ways to go sideways if you're not careful about your traversal order.

Questions Asked (1)

Q1

Given an n x n binary matrix where 1s represent land and 0s represent water, and there are exactly two islands, what is the minimum number of 0s you need to flip to connect the two islands into one?

Algorithms & Data Structures
Author's notes

My first instinct was just BFS from one island and count steps to reach the other, which is roughly right but I fumbled the setup.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Model the problem as finding the shortest path between the two islands, where the cost is the number of water cells traversed. Use multi-source BFS starting from all cells of one island, expanding through water cells, and stop when reaching any cell of the other island. The distance at that point is the minimum number of 0s to flip.

Pro tip: Clarify that flipping a 0 to 1 connects it to adjacent land, so the problem reduces to finding the minimum number of water cells to cross. Mention that BFS is optimal because all edges have equal weight (each water cell costs 1).

1. Identify the two islands

Use DFS or BFS to label all cells of the first island (e.g., mark them as 2) and collect their coordinates. The second island remains as 1s.

2. Initialize multi-source BFS

Enqueue all cells of the first island with distance 0. Use a queue for BFS and a visited set or distance matrix to track the minimum steps to each cell.

3. Expand through water cells

While the queue is not empty, pop a cell and explore its 4-directional neighbors. If a neighbor is water (0) and not visited, mark it visited with distance+1 and enqueue it. If a neighbor belongs to the second island (1), return the current distance+1 as the answer.

4. Return the minimum flips

The first time you reach a cell of the second island, the distance value (number of water cells flipped) is the minimum. Return that value.

Key Points to Mention

  • BFS guarantees shortest path in unweighted graph (each water cell costs 1).
  • Multi-source BFS from all cells of one island simultaneously to find minimum distance to the other island.
  • Time complexity O(n^2) since each cell is visited at most once.
  • Space complexity O(n^2) for the queue and visited set.
  • Edge cases: islands may be adjacent (answer 0), or separated by large water bodies.
  • Alternative approach: DFS to find islands, then BFS; or use 0-1 BFS if considering different costs, but here uniform cost.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.