Number of Islands: Optimal Solution (Data-Backed Guide)

By DSA Prep Team · March 4, 2026 · 9 min read · Algorithms

Number of Islands is the #8 most asked LeetCode problem globally — and the canonical entry point to Graph / Grid traversal in interviews.

Our analysis of 10,385 verified interview questions across 259 companies shows it appeared 92 times across 44 companies — including Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, Citadel, Cloudflare, DoorDash, Dropbox, and CrowdStrike.

This problem teaches you the fundamental flood fill / connected components pattern that unlocks dozens of grid and graph problems. Master DFS here, understand BFS as an alternative, and learn Union Find for the follow-up — and you'll handle nearly any grid traversal question in an interview.

The Data: 44 Companies Ask This
Problem Statement
The Core Intuition: Flood Fill
Approach 1: DFS (Recommended)
Approach 2: BFS
Code in Python, Java & JavaScript
Complexity Analysis
Grid Problem Family
How to Actually Remember This

The Data: 44 Companies Ask This

Metric	Value
Total Interview Appearances	92 verified mentions
Companies That Ask It	44 companies
Global Rank	#8 out of 10,385 questions
Difficulty	Medium
Core Patterns	DFS, BFS, Union Find, Matrix

📌 Companies That Ask This Problem

Google, Amazon, Meta, Microsoft, Bloomberg, Goldman Sachs, Citadel, Cloudflare, DoorDash, Dropbox, CrowdStrike, Cisco, Capital One, ByteDance, Expedia, Flipkart, Goldman Sachs, Grammarly, HPE, Infosys, Intel, Intuit, LinkedIn, Lucid, Moloco, Morgan Stanley, and 18 more.

Problem Statement

LeetCode #200 — Number of Islands

Given an m x n 2D binary grid where '1' represents land and '0' represents water, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Example

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

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

The Core Intuition: Flood Fill

Scan every cell. When you find an unvisited '1', you've discovered a new island — increment counter. Then flood fill from that cell: recursively mark all connected '1's as visited (set to '0' or use a visited set). This ensures each island is counted exactly once.

💡 Why Mutate the Grid?

Setting visited land cells to '0' directly in the grid is the cleanest O(1) space way to track visited cells. It avoids a separate visited array or set. If you can't mutate the input, use a set of visited coordinates — same logic, O(m×n) extra space.

Approach 1: DFS

For each unvisited '1', run DFS in all 4 directions, marking visited cells as '0'. Each DFS call explores one complete island.

Approach 2: BFS

Same idea but use a queue instead of recursion. BFS is preferred when the grid is very large and recursion depth could cause a stack overflow.

Code in Python, Java & JavaScript

Python 3 — DFS

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0':
            return
        grid[r][c] = '0'  # mark as visited
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                dfs(r, c)

    return count

Python 3 — BFS

from collections import deque

def numIslands(grid: list[list[str]]) -> int:
    if not grid:
        return 0

    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                queue = deque([(r, c)])
                grid[r][c] = '0'

                while queue:
                    row, col = queue.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = row+dr, col+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            queue.append((nr, nc))
                            grid[nr][nc] = '0'

    return count

Java — DFS

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int r = 0; r < grid.length; r++) {
            for (int c = 0; c < grid[0].length; c++) {
                if (grid[r][c] == '1') {
                    count++;
                    dfs(grid, r, c);
                }
            }
        }
        return count;
    }

    private void dfs(char[][] grid, int r, int c) {
        if (r < 0 || r >= grid.length || c < 0 || c >= grid[0].length || grid[r][c] == '0') return;
        grid[r][c] = '0';
        dfs(grid, r+1, c); dfs(grid, r-1, c);
        dfs(grid, r, c+1); dfs(grid, r, c-1);
    }
}

JavaScript — DFS

var numIslands = function(grid) {
    const rows = grid.length, cols = grid[0].length;
    let count = 0;

    const dfs = (r, c) => {
        if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;
        grid[r][c] = '0';
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1);
    };

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (grid[r][c] === '1') { count++; dfs(r, c); }
        }
    }
    return count;
};

Complexity Analysis

        📊 Complexity Summary
        Time: O(m × n) — Every cell is visited at most once (either skipped as '0' or explored and marked '0').
Space: O(m × n) — DFS recursion stack in the worst case (entire grid is one island). BFS queue also O(m × n) worst case. Use BFS on very large grids to avoid stack overflow.

    

Grid Problem Family

Problem	Pattern	Key Difference
LC #200 Number of Islands	DFS/BFS flood fill	Count connected components
LC #130 Surrounded Regions	DFS from border	Flood fill from edges inward
LC #417 Pacific Atlantic	Multi-source BFS	Run BFS from both oceans
LC #695 Max Area of Island	DFS with size tracking	Return max component size
LC #286 Walls and Gates	Multi-source BFS	BFS from all gates at once
LC #1020 Number of Enclaves	DFS from border	Count land not reachable from edge

How to Actually Remember This

        ✅ Your Spaced Repetition Schedule
        Today: Solve LC #200 with DFS. Then immediately solve LC #695 (Max Area of Island) — same pattern, track size.
Day 3: Solve LC #130 (Surrounded Regions) — DFS from border, then flip.
Day 7: Solve LC #417 (Pacific Atlantic Water Flow) — multi-source BFS from two sides.
Day 14: Solve LC #286 (Walls and Gates) — multi-source BFS from all gates simultaneously.

    

Tag all grid problems on DSAPrep.dev under Graph, DFS, and BFS.

Track on DSAPrep.dev →

Table of Contents