PracHub
QuestionsPremiumCoachesLearningGuidesInterview Prep

Quick Overview

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

  • Medium
  • Coupang
  • Coding & Algorithms
  • Software Engineer

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.

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return -1

    n = len(grid)
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    queue = deque()

    found = False
    for r in range(n):
        if found:
            break
        for c in range(n):
            if grid[r][c] == 1:
                stack = [(r, c)]
                grid[r][c] = 2
                found = True
                while stack:
                    x, y = stack.pop()
                    queue.append((x, y))
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < n and 0 <= ny < n and grid[nx][ny] == 1:
                            grid[nx][ny] = 2
                            stack.append((nx, ny))
                break

    flips = 0
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < n and 0 <= ny < n:
                    if grid[nx][ny] == 1:
                        return flips
                    if grid[nx][ny] == 0:
                        grid[nx][ny] = 2
                        queue.append((nx, ny))
        flips += 1

    return -1

Time complexity: O(n^2). Space complexity: O(n^2) in the worst case for the BFS queue/stack.

Hints

  1. First mark all cells of one island, then treat them as simultaneous BFS starting points.
  2. 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.

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return [0, -1]

    rows, cols = len(grid), len(grid[0])
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    start = None

    for r in range(rows):
        if start is not None:
            break
        for c in range(cols):
            if grid[r][c] == 1:
                start = (r, c)
                break

    if start is None:
        return [0, -1]

    queue = deque()
    stack = [start]
    grid[start[0]][start[1]] = 2
    first_island_size = 0

    while stack:
        x, y = stack.pop()
        first_island_size += 1
        queue.append((x, y))
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == 1:
                grid[nx][ny] = 2
                stack.append((nx, ny))

    flips = 0
    while queue:
        for _ in range(len(queue)):
            x, y = queue.popleft()
            for dx, dy in directions:
                nx, ny = x + dx, y + dy
                if 0 <= nx < rows and 0 <= ny < cols:
                    if grid[nx][ny] == 1:
                        return [first_island_size, flips]
                    if grid[nx][ny] == 0:
                        grid[nx][ny] = 2
                        queue.append((nx, ny))
        flips += 1

    return [first_island_size, -1]

Time complexity: O(rows * cols). Space complexity: O(rows * cols) in the worst case for the stack and BFS queue.

Hints

  1. Use an explicit stack or queue to collect every cell in the first island.
  2. 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.

Solution

def solution(grid):
    if not grid or not grid[0]:
        return 0

    rows, cols = len(grid), len(grid[0])
    visited = [[False] * cols for _ in range(rows)]
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    best = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 1 and not visited[r][c]:
                visited[r][c] = True
                stack = [(r, c)]
                size = 0

                while stack:
                    x, y = stack.pop()
                    size += 1
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        if 0 <= nx < rows and 0 <= ny < cols:
                            if grid[nx][ny] == 1 and not visited[nx][ny]:
                                visited[nx][ny] = True
                                stack.append((nx, ny))

                best = max(best, size)

    return best

Time complexity: O(rows * cols). Space complexity: O(rows * cols) for the visited grid plus the explicit stack.

Hints

  1. Replace recursive calls with an explicit stack or queue of cells to visit.
  2. 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.

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return -1

    rows, cols = len(grid), len(grid[0])
    total = rows * cols
    start = -1

    for cell in range(total):
        r = cell // cols
        c = cell % cols
        if grid[r][c] == 1:
            start = cell
            break

    if start == -1:
        return -1

    queue = deque()
    stack = [start]
    grid[start // cols][start % cols] = 2

    while stack:
        cell = stack.pop()
        queue.append(cell)
        r = cell // cols
        c = cell % cols

        if r > 0:
            nxt = cell - cols
            if grid[r - 1][c] == 1:
                grid[r - 1][c] = 2
                stack.append(nxt)
        if r + 1 < rows:
            nxt = cell + cols
            if grid[r + 1][c] == 1:
                grid[r + 1][c] = 2
                stack.append(nxt)
        if c > 0:
            nxt = cell - 1
            if grid[r][c - 1] == 1:
                grid[r][c - 1] = 2
                stack.append(nxt)
        if c + 1 < cols:
            nxt = cell + 1
            if grid[r][c + 1] == 1:
                grid[r][c + 1] = 2
                stack.append(nxt)

    flips = 0
    while queue:
        level_count = len(queue)
        for _ in range(level_count):
            cell = queue.popleft()
            r = cell // cols
            c = cell % cols

            if r > 0:
                nxt = cell - cols
                value = grid[r - 1][c]
                if value == 1:
                    return flips
                if value == 0:
                    grid[r - 1][c] = 2
                    queue.append(nxt)
            if r + 1 < rows:
                nxt = cell + cols
                value = grid[r + 1][c]
                if value == 1:
                    return flips
                if value == 0:
                    grid[r + 1][c] = 2
                    queue.append(nxt)
            if c > 0:
                nxt = cell - 1
                value = grid[r][c - 1]
                if value == 1:
                    return flips
                if value == 0:
                    grid[r][c - 1] = 2
                    queue.append(nxt)
            if c + 1 < cols:
                nxt = cell + 1
                value = grid[r][c + 1]
                if value == 1:
                    return flips
                if value == 0:
                    grid[r][c + 1] = 2
                    queue.append(nxt)

        flips += 1

    return -1

Time complexity: O(rows * cols). Space complexity: O(rows * cols) in the worst case for the stack and BFS queue; no extra visited matrix is used.

Hints

  1. Encode a cell as one integer id = row * cols + col instead of storing many coordinate tuples.
  2. 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.

Solution

def solution(grid):
    from collections import deque

    if not grid or not grid[0]:
        return -1

    rows, cols = len(grid), len(grid[0])
    total = rows * cols
    start = -1

    for cell in range(total):
        r = cell // cols
        c = cell % cols
        if grid[r][c] == 1:
            start = cell
            break

    if start == -1:
        return -1

    visited = bytearray(total)
    stack = [start]
    queue = deque()
    visited[start] = 1

    while stack:
        cell = stack.pop()
        queue.append(cell)
        r = cell // cols
        c = cell % cols

        neighbors = []
        if r > 0:
            neighbors.append(cell - cols)
        if r + 1 < rows:
            neighbors.append(cell + cols)
        if c > 0:
            neighbors.append(cell - 1)
        if c + 1 < cols:
            neighbors.append(cell + 1)

        for nxt in neighbors:
            nr = nxt // cols
            nc = nxt % cols
            if not visited[nxt] and grid[nr][nc] == 1:
                visited[nxt] = 1
                stack.append(nxt)

    flips = 0
    while queue:
        for _ in range(len(queue)):
            cell = queue.popleft()
            r = cell // cols
            c = cell % cols

            neighbors = []
            if r > 0:
                neighbors.append(cell - cols)
            if r + 1 < rows:
                neighbors.append(cell + cols)
            if c > 0:
                neighbors.append(cell - 1)
            if c + 1 < cols:
                neighbors.append(cell + 1)

            for nxt in neighbors:
                if visited[nxt]:
                    continue
                nr = nxt // cols
                nc = nxt % cols
                if grid[nr][nc] == 1:
                    return flips
                visited[nxt] = 1
                queue.append(nxt)

        flips += 1

    return -1

Time complexity: O(rows * cols). Space complexity: O(rows * cols) for the visited bytearray plus the traversal queues.

Hints

  1. Use a separate visited structure instead of marking cells inside grid.
  2. Once the first island is fully marked in visited, any unvisited land cell reached by BFS belongs to the second island.
Last updated: Jun 14, 2026

Related Coding Questions

  • Find shortest distance between two islands - Coupang (medium)
  • Sort products by price and attention score - Coupang (Medium)

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.