Remove Islands

Tags

Remove Islands

Category

Graphs

Difficulty

Medium

Problem Statement

Given a two-dimensional matrix of 0s and 1s, remove all "islands" from the matrix. An island is a group of connected 1s (horizontally or vertically adjacent) that is not connected to any 1 on the border of the matrix. Removing an island means setting all its 1s to 0s. Modify the matrix in place and return it.

Intuition

Instead of finding islands to remove, it is easier to find the 1s that should be kept -- those connected to the border. Any 1 reachable from a border 1 via horizontal/vertical adjacency is safe. All other 1s are islands and should be removed.

We perform a traversal (BFS or DFS) starting from every border cell that contains a 1, marking all reachable 1s as "safe." After processing all border cells, any 1 that was not marked safe is part of an island and gets set to 0.

Approach

  1. Iterate through all border cells of the matrix.
  2. For each border cell containing a 1, perform a BFS/DFS to mark all connected 1s as safe (e.g., temporarily set them to 2, or use a separate boolean matrix).
  3. Iterate through all cells:
    • If a cell is marked safe (2), set it back to 1.
    • If a cell is still 1 (not marked safe), set it to 0.

Pseudocode

function removeIslands(matrix):
    rows = number of rows
    cols = number of columns

    // Mark all border-connected 1s
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if isBorder(i, j, rows, cols) and matrix[i][j] == 1:
                markConnected(matrix, i, j)  // mark as 2

    // Clean up
    for i from 0 to rows - 1:
        for j from 0 to cols - 1:
            if matrix[i][j] == 2:
                matrix[i][j] = 1
            else if matrix[i][j] == 1:
                matrix[i][j] = 0

    return matrix

function markConnected(matrix, i, j):
    queue = [(i, j)]
    matrix[i][j] = 2
    while queue is not empty:
        (row, col) = queue.dequeue()
        for (newRow, newCol) in neighbors(row, col):
            if inBounds(newRow, newCol) and matrix[newRow][newCol] == 1:
                matrix[newRow][newCol] = 2
                queue.enqueue((newRow, newCol))

Time & Space Complexity

  • Time: O(n * m), where n and m are the dimensions of the matrix. Each cell is visited at most once.
  • Space: O(n * m) for the BFS queue in the worst case. Using a separate boolean matrix also uses O(n * m). The in-place marking approach (using value 2) avoids extra space for visited tracking.

Key Insights

  • Inverting the problem ("what to keep" instead of "what to remove") simplifies the logic significantly.
  • Starting from the border guarantees we find all non-island 1s.
  • In-place marking with a temporary value (2) avoids needing a separate visited matrix.
  • This same pattern appears in problems like "surrounded regions" in other contexts.

Edge Cases

  • Matrix with all 0s: nothing to remove, return as-is.
  • Matrix with all 1s: all cells are border-connected, nothing removed.
  • No interior cells (matrix smaller than 3x3): no islands possible.
  • All 1s are on the border: nothing is removed.
  • All 1s are in the interior with no border connection: all interior 1s are removed.

Linked mentions