Skip to main content

Island Problems

A collection of classic grid/matrix traversal problems using DFS/BFS. These problems share a common pattern of exploring connected components in a 2D grid.

[!TIP] Common Pattern: Most island problems use the same DFS/BFS template—iterate through cells, and when you find an unvisited land cell, explore all connected land cells.

Number of Islands​

LeetCode 200 | Difficulty: Medium​

Problem Description​

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Constraints​

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 300
  • grid[i][j] is '0' or '1'

Example​

Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Visual Representation:

┌───┬───┬───┬───┬───┐
│ 1 │ 1 │ 0 │ 0 │ 0 │  ← Island 1
├───┼───┼───┼───┼───┤
│ 1 │ 1 │ 0 │ 0 │ 0 │
├───┼───┼───┼───┼───┤
│ 0 │ 0 │ 1 │ 0 │ 0 │  ← Island 2
├───┼───┼───┼───┼───┤
│ 0 │ 0 │ 0 │ 1 │ 1 │  ← Island 3
└───┴───┴───┴───┴───┘

Complexity​

  • Time: $O(M \times N)$ — Each cell visited at most once
  • Space: $O(M \times N)$ — Visited array + recursion stack (worst case)

Solution​

public int NumIslands(char[][] grid)
{
    int m = grid.Length, n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int count = 0;
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == '1' && !visited[i, j])
            {
                DFS(grid, visited, i, j);
                count++; // Found a new island
            }
        }
    }
    return count;
}

void DFS(char[][] grid, bool[,] visited, int i, int j)
{
    // Boundary check + water check + visited check
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length 
        || visited[i, j] || grid[i][j] == '0')
        return;

    visited[i, j] = true;
    
    // Explore all 4 directions
    DFS(grid, visited, i - 1, j); // up
    DFS(grid, visited, i + 1, j); // down
    DFS(grid, visited, i, j - 1); // left
    DFS(grid, visited, i, j + 1); // right
}

Max Area of Island​

LeetCode 695 | Difficulty: Medium​

Problem Description​

You are given an m x n binary matrix grid. An island is a group of 1s connected 4-directionally. Return the maximum area of an island in grid. If there is no island, return 0.

Constraints​

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is 0 or 1

Example​

Input: grid = [
  [0,0,1,0,0,0,0,1,0,0,0,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,1,1,0,1,0,0,0,0,0,0,0,0],
  [0,1,0,0,1,1,0,0,1,0,1,0,0],
  [0,1,0,0,1,1,0,0,1,1,1,0,0],
  [0,0,0,0,0,0,0,0,0,0,1,0,0],
  [0,0,0,0,0,0,0,1,1,1,0,0,0],
  [0,0,0,0,0,0,0,1,1,0,0,0,0]
]
Output: 6
Explanation: The largest island has area 6 (the connected 1s on the right side).

Complexity​

  • Time: $O(M \times N)$
  • Space: $O(M \times N)$

Solution​

public int MaxAreaOfIsland(int[][] grid)
{
    int m = grid.Length, n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int maxArea = 0;
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1 && !visited[i, j])
            {
                maxArea = Math.Max(maxArea, DFS(grid, visited, i, j));
            }
        }
    }
    return maxArea;
}

int DFS(int[][] grid, bool[,] visited, int i, int j)
{
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length 
        || grid[i][j] == 0 || visited[i, j])
        return 0;
    
    visited[i, j] = true;
    int area = 1; // Count current cell
    
    area += DFS(grid, visited, i - 1, j);
    area += DFS(grid, visited, i + 1, j);
    area += DFS(grid, visited, i, j - 1);
    area += DFS(grid, visited, i, j + 1);
    
    return area;
}

Island Perimeter​

LeetCode 463 | Difficulty: Easy​

Problem Description​

You are given a row x col grid where grid[i][j] = 1 represents land and grid[i][j] = 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island.

Return the perimeter of the island.

Constraints​

  • row == grid.length
  • col == grid[i].length
  • 1 <= row, col <= 100
  • grid[i][j] is 0 or 1
  • There is exactly one island

Example​

Input: grid = [
  [0,1,0,0],
  [1,1,1,0],
  [0,1,0,0],
  [1,1,0,0]
]
Output: 16

Visual Explanation:

Each land cell contributes 4 edges initially.
Subtract 1 for each adjacent land cell.

    ┌───┐
    │ 1 │     ← 3 edges (top, left, right)
┌───┼───┼───┐
│ 1 │ 1 │ 1 │ ← outer edges only
└───┼───┼───┘
    │ 1 │
┌───┼───┤
│ 1 │ 1 │
└───┴───┘

Complexity​

  • Time: $O(M \times N)$
  • Space: $O(1)$

Solution​

public int IslandPerimeter(int[][] grid)
{
    int m = grid.Length, n = grid[0].Length;
    int perimeter = 0;
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 1)
            {
                // Check all 4 neighbors - add 1 for each water/boundary
                int left  = (i > 0) ? grid[i - 1][j] : 0;
                int right = (i < m - 1) ? grid[i + 1][j] : 0;
                int up    = (j > 0) ? grid[i][j - 1] : 0;
                int down  = (j < n - 1) ? grid[i][j + 1] : 0;
                
                perimeter += (left == 0 ? 1 : 0) +
                             (right == 0 ? 1 : 0) +
                             (up == 0 ? 1 : 0) +
                             (down == 0 ? 1 : 0);
            }
        }
    }
    return perimeter;
}

Number of Closed Islands​

LeetCode 1254 | Difficulty: Medium​

Problem Description​

Given a 2D grid consisting of 0s (land) and 1s (water), an island is a maximal 4-directionally connected group of 0s. A closed island is an island totally surrounded by 1s (not touching any edge).

Return the number of closed islands.

Constraints​

  • 1 <= grid.length, grid[0].length <= 100
  • 0 <= grid[i][j] <= 1

Example​

Input: grid = [
  [1,1,1,1,1,1,1,0],
  [1,0,0,0,0,1,1,0],
  [1,0,1,0,1,1,1,0],
  [1,0,0,0,0,1,0,1],
  [1,1,1,1,1,1,1,0]
]
Output: 2

Complexity​

  • Time: $O(M \times N)$
  • Space: $O(M \times N)$

Solution​

public int ClosedIsland(int[][] grid)
{
    int m = grid.Length, n = grid[0].Length;
    bool[,] visited = new bool[m, n];
    int count = 0;
    
    for (int i = 0; i < m; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (grid[i][j] == 0 && !visited[i, j])
            {
                bool touchesBorder = false;
                DFS(grid, visited, i, j, ref touchesBorder);
                if (!touchesBorder) count++;
            }
        }
    }
    return count;
}

void DFS(int[][] grid, bool[,] visited, int i, int j, ref bool touchesBorder)
{
    if (i < 0 || i >= grid.Length || j < 0 || j >= grid[0].Length 
        || visited[i, j] || grid[i][j] == 1)
        return;

    // Check if this cell is on the border
    touchesBorder = touchesBorder || 
        (i == 0 || i == grid.Length - 1 || j == 0 || j == grid[0].Length - 1);
    
    visited[i, j] = true;
    DFS(grid, visited, i - 1, j, ref touchesBorder);
    DFS(grid, visited, i + 1, j, ref touchesBorder);
    DFS(grid, visited, i, j - 1, ref touchesBorder);
    DFS(grid, visited, i, j + 1, ref touchesBorder);
}

Number of Islands II​

LeetCode 305 | Difficulty: Hard 🔒​

Problem Description​

You are given an empty 2D binary grid of size m x n. Initially, all cells are water (0). You may perform addLand operations which turns a water cell into land.

Return an array of integers where answer[i] is the number of islands after the ith operation.

Constraints​

  • 1 <= m, n, positions.length <= 10^4
  • 1 <= m * n <= 10^4
  • positions[i].length == 2
  • 0 <= ri < m
  • 0 <= ci < n

Approach​

[!IMPORTANT] This problem requires Union-Find for optimal $O(k \cdot \alpha(mn))$ time complexity. Simple DFS would be $O(k \times m \times n)$ which is too slow.

Union-Find Approach:

  1. Initialize each cell as its own "island" when added
  2. When adding a new land cell, check all 4 neighbors
  3. If a neighbor is also land, union them (merge islands)
  4. Track the count of distinct islands

Solution (Union-Find)​

public IList<int> NumIslands2(int m, int n, int[][] positions)
{
    List<int> result = new List<int>();
    int[] parent = new int[m * n];
    int[] rank = new int[m * n];
    Array.Fill(parent, -1); // -1 means water
    
    int count = 0;
    int[] dirs = {0, 1, 0, -1, 0};
    
    foreach (var pos in positions)
    {
        int i = pos[0], j = pos[1];
        int id = i * n + j;
        
        if (parent[id] != -1) // Already land (duplicate position)
        {
            result.Add(count);
            continue;
        }
        
        parent[id] = id; // New island
        count++;
        
        // Check 4 neighbors
        for (int d = 0; d < 4; d++)
        {
            int ni = i + dirs[d], nj = j + dirs[d + 1];
            int nid = ni * n + nj;
            
            if (ni >= 0 && ni < m && nj >= 0 && nj < n && parent[nid] != -1)
            {
                if (Union(parent, rank, id, nid))
                    count--; // Merged two islands
            }
        }
        result.Add(count);
    }
    return result;
}

int Find(int[] parent, int x)
{
    if (parent[x] != x)
        parent[x] = Find(parent, parent[x]); // Path compression
    return parent[x];
}

bool Union(int[] parent, int[] rank, int x, int y)
{
    int px = Find(parent, x), py = Find(parent, y);
    if (px == py) return false; // Already same island
    
    // Union by rank
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
    
    return true;
}

Interview Tips​

  • DFS vs BFS: Both work for island problems; DFS is simpler to write, BFS avoids stack overflow on large grids
  • Modify grid in-place?: Can mark visited by changing '1' to '0' to save space, but discuss trade-offs
  • 8-directional variants: Some problems count diagonal connections—add 4 more directions
  • Common follow-ups:
    • What if the grid is too large to fit in memory? → Streaming/chunking
    • What if we need to support dynamic updates? → Union-Find