How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Coupang.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Coupang during technical interviews.

Compute minimal flips connecting two islands

Company: Coupang

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given an n x n binary grid of 0s (water) and 1s (land) containing exactly two disjoint islands (cells with 1 connected 4-directionally), return the minimum number of 0-cells that must be flipped to 1 to connect the two islands via a 4-directional path of 1s. Describe your algorithm, justify its correctness, and analyze time and space complexity. Follow-ups: (a) Implement an approach that first identifies one island and then expands outward to find the other; (b) Explain techniques to avoid recursion stack overflow when discovering an island; (c) Discuss scalability for grids up to 2000 x 2000; (d) Provide a solution that avoids mutating the input grid if required.

Quick Answer: This question evaluates grid/graph traversal, connectivity and shortest-path reasoning, along with complexity analysis and handling of large inputs and input immutability.

Part 1: Minimum Water Flips to Connect Two Islands

You are given an n x n binary grid containing exactly two disjoint islands. An island is a group of 1-cells connected 4-directionally. Return the minimum number of 0-cells that must be flipped to 1 so that the two islands become connected by a 4-directional path.

Constraints

2 <= n <= 500
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: 1

Explanation: The islands are diagonal. Flipping either remaining water cell connects them.

Input: ([[1, 0, 0], [0, 0, 0], [0, 0, 1]],)

Expected Output: 3

Explanation: The shortest 4-directional connection has three water cells between the two corner islands.

Input: ([[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]],)

Expected Output: 1

Explanation: The center island is separated from the surrounding island by one layer of water.

Input: ([[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0]],)

Expected Output: 3

Explanation: The closest cells of the two islands have Manhattan distance 4, so 3 water cells must be flipped.

Hints

First mark all cells of one island, then treat them as simultaneous BFS starting points.
The BFS layer number represents how many water cells have been flipped so far.

Part 2: Identify One Island, Then Expand Outward

You are given a binary grid containing exactly two disjoint islands. First identify the island that contains the lexicographically smallest land cell, meaning the first 1 encountered in row-major order. Then expand outward from all cells of that island until reaching the other island. Return both the size of the first island and the minimum number of water cells that must be flipped to connect the islands.

Constraints

1 <= rows, cols <= 500
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: [1, 1]

Explanation: The first island is the single cell at row 0, column 1. One flip connects it to the other island.

Input: ([[1, 1, 0, 1]],)

Expected Output: [2, 1]

Explanation: The first island has two cells. Flipping the middle water cell connects it to the right island.

Input: ([[0, 0, 0], [0, 1, 0], [0, 0, 1]],)

Expected Output: [1, 1]

Explanation: The first island is one cell, diagonally separated from the second island.

Input: ([[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]],)

Expected Output: [16, 1]

Explanation: The first island is the outer ring with 16 cells. One flip connects it to the center island.

Hints

Use an explicit stack or queue to collect every cell in the first island.
After collecting the island, run a multi-source BFS from all its cells at once.

Part 3: Discover Islands Without Recursion

Recursive DFS can overflow the call stack on large or skinny islands. Given a binary grid, return the size of the largest 4-directionally connected island of 1s using an iterative traversal. The input may contain zero, one, or many islands.

Constraints

0 <= rows <= 1000
0 <= cols <= 1000
grid[i][j] is either 0 or 1
Do not use recursive DFS

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no islands.

Input: ([[1]],)

Expected Output: 1

Explanation: A single land cell forms an island of size 1.

Input: ([[0, 0], [0, 0]],)

Expected Output: 0

Explanation: There are no land cells.

Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)

Expected Output: 3

Explanation: The largest island contains the connected cells at the top-left.

Input: ([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],)

Expected Output: 10

Explanation: A long skinny island should be handled iteratively rather than recursively.

Hints

Replace recursive calls with an explicit stack or queue of cells to visit.
Mark cells as visited as soon as you push them, not when you pop them, to avoid duplicate pushes.

Part 4: Scalable Shortest Bridge for Very Large Grids

You are given a rectangular binary grid with exactly two disjoint islands. The grid may be as large as 2000 x 2000, so the algorithm must avoid recursion and should avoid unnecessary per-cell object overhead. Return the minimum number of water cells that must be flipped to connect the islands.

Constraints

1 <= rows, cols <= 2000
rows * cols <= 4,000,000
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid
Use an iterative approach; recursive DFS is not suitable at this scale

Examples

Input: ([[1, 0, 1]],)

Expected Output: 1

Explanation: A single water cell separates the two islands in a one-row grid.

Input: ([[1], [0], [0], [1]],)

Expected Output: 2

Explanation: Two water cells must be flipped in the single column.

Input: ([[1, 1, 0, 0, 0], [1, 1, 0, 1, 1]],)

Expected Output: 1

Explanation: The closest bridge is through the water cell at row 1, column 2.

Input: ([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]],)

Expected Output: 4

Explanation: The corner islands have Manhattan distance 5, so 4 water cells are between them.

Hints

Encode a cell as one integer id = row * cols + col instead of storing many coordinate tuples.
Mark cells directly in the grid to avoid keeping a separate visited matrix.

Part 5: Shortest Bridge Without Mutating the Input Grid

You are given a binary grid containing exactly two disjoint islands. Return the minimum number of water cells that must be flipped to connect the islands, but do not modify grid. This is useful when callers need to reuse the original data after the function returns.

Constraints

1 <= rows, cols <= 1000
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
Do not write to grid or any of its rows

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: 1

Explanation: The diagonal islands need one water flip, and the original grid should not be changed.

Input: ([[1, 1, 0, 0, 1]],)

Expected Output: 2

Explanation: Two water cells separate the left island from the right island.

Input: ([[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]],)

Expected Output: 1

Explanation: The center island is one water layer away from the outer island.

Input: ([[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]],)

Expected Output: 2

Explanation: The shortest bridge between the vertical upper island and lower-left island flips two water cells.

Hints

Use a separate visited structure instead of marking cells inside grid.
Once the first island is fully marked in visited, any unvisited land cell reached by BFS belongs to the second island.

Compute minimal flips connecting two islands

Company: Coupang

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Quick Answer: This question evaluates grid/graph traversal, connectivity and shortest-path reasoning, along with complexity analysis and handling of large inputs and input immutability.

Part 1: Minimum Water Flips to Connect Two Islands

Constraints

2 <= n <= 500
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: 1

Explanation: The islands are diagonal. Flipping either remaining water cell connects them.

Input: ([[1, 0, 0], [0, 0, 0], [0, 0, 1]],)

Expected Output: 3

Explanation: The shortest 4-directional connection has three water cells between the two corner islands.

Input: ([[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]],)

Expected Output: 1

Explanation: The center island is separated from the surrounding island by one layer of water.

Input: ([[1, 1, 0, 0, 0], [1, 0, 0, 0, 0], [0, 0, 0, 1, 1], [0, 0, 0, 0, 1], [0, 0, 0, 0, 0]],)

Expected Output: 3

Explanation: The closest cells of the two islands have Manhattan distance 4, so 3 water cells must be flipped.

Hints

First mark all cells of one island, then treat them as simultaneous BFS starting points.
The BFS layer number represents how many water cells have been flipped so far.

Part 2: Identify One Island, Then Expand Outward

Constraints

1 <= rows, cols <= 500
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: [1, 1]

Explanation: The first island is the single cell at row 0, column 1. One flip connects it to the other island.

Input: ([[1, 1, 0, 1]],)

Expected Output: [2, 1]

Explanation: The first island has two cells. Flipping the middle water cell connects it to the right island.

Input: ([[0, 0, 0], [0, 1, 0], [0, 0, 1]],)

Expected Output: [1, 1]

Explanation: The first island is one cell, diagonally separated from the second island.

Input: ([[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]],)

Expected Output: [16, 1]

Explanation: The first island is the outer ring with 16 cells. One flip connects it to the center island.

Hints

Use an explicit stack or queue to collect every cell in the first island.
After collecting the island, run a multi-source BFS from all its cells at once.

Part 3: Discover Islands Without Recursion

Constraints

0 <= rows <= 1000
0 <= cols <= 1000
grid[i][j] is either 0 or 1
Do not use recursive DFS

Examples

Input: ([],)

Expected Output: 0

Explanation: An empty grid has no islands.

Input: ([[1]],)

Expected Output: 1

Explanation: A single land cell forms an island of size 1.

Input: ([[0, 0], [0, 0]],)

Expected Output: 0

Explanation: There are no land cells.

Input: ([[1, 1, 0], [0, 1, 0], [1, 0, 1]],)

Expected Output: 3

Explanation: The largest island contains the connected cells at the top-left.

Input: ([[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]],)

Expected Output: 10

Explanation: A long skinny island should be handled iteratively rather than recursively.

Hints

Replace recursive calls with an explicit stack or queue of cells to visit.
Mark cells as visited as soon as you push them, not when you pop them, to avoid duplicate pushes.

Part 4: Scalable Shortest Bridge for Very Large Grids

Constraints

1 <= rows, cols <= 2000
rows * cols <= 4,000,000
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
The solution may mutate the input grid
Use an iterative approach; recursive DFS is not suitable at this scale

Examples

Input: ([[1, 0, 1]],)

Expected Output: 1

Explanation: A single water cell separates the two islands in a one-row grid.

Input: ([[1], [0], [0], [1]],)

Expected Output: 2

Explanation: Two water cells must be flipped in the single column.

Input: ([[1, 1, 0, 0, 0], [1, 1, 0, 1, 1]],)

Expected Output: 1

Explanation: The closest bridge is through the water cell at row 1, column 2.

Input: ([[1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 1]],)

Expected Output: 4

Explanation: The corner islands have Manhattan distance 5, so 4 water cells are between them.

Hints

Encode a cell as one integer id = row * cols + col instead of storing many coordinate tuples.
Mark cells directly in the grid to avoid keeping a separate visited matrix.

Part 5: Shortest Bridge Without Mutating the Input Grid

Constraints

1 <= rows, cols <= 1000
grid[i][j] is either 0 or 1
The grid contains exactly two disjoint 4-directionally connected islands
Do not write to grid or any of its rows

Examples

Input: ([[0, 1], [1, 0]],)

Expected Output: 1

Explanation: The diagonal islands need one water flip, and the original grid should not be changed.

Input: ([[1, 1, 0, 0, 1]],)

Expected Output: 2

Explanation: Two water cells separate the left island from the right island.

Input: ([[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]],)

Expected Output: 1

Explanation: The center island is one water layer away from the outer island.

Input: ([[0, 0, 1, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 0, 0], [1, 1, 0, 0, 0], [0, 1, 0, 0, 0]],)

Expected Output: 2

Explanation: The shortest bridge between the vertical upper island and lower-left island flips two water cells.

Hints

Use a separate visited structure instead of marking cells inside grid.
Once the first island is fully marked in visited, any unvisited land cell reached by BFS belongs to the second island.

Quick Overview

Quick Overview