Skip to content

Volume ITechnology

4.20.1 — Number of Islands ​

LeetCode 200 · Medium · ★ Blind 75

The problem ​

Count the islands in a grid of '1' (land) and '0' (water). Cells connect horizontally and vertically, not diagonally.

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0        →  3
0 0 0 1 1

In plain English, we are given a 2D matrix representing a map. 1s are land and 0s are water. An island is formed by connecting adjacent lands horizontally or vertically (diagonals do not count). We need to return the total number of distinct islands. The grid dimensions can range up to 300x300. Edge cases to consider include an empty grid, a grid entirely made of water (returns 0), or a grid entirely made of land (returns 1).

The pattern ​

Scan every cell. When you meet a piece of land that has not been seen yet, that is a new island — so add one to the count, then flood the entire island so its other cells are never counted again.

The flood is a DFS or BFS from that cell, marking everything it reaches.

The guard "only start from an unvisited cell" is the whole algorithm. It is the same idea as the run-start check in 4.4.9 Longest Consecutive Sequence: do the work only from one agreed member of each group.

A picture to hold in mind ​

Think of the grid as a physical map on a table, and you are holding a bucket of red paint. You read the map like a book—left to right, top to bottom. Every time you find an unpainted piece of land ('1'), you know you've discovered a new island. You immediately pour the red paint on it. The paint spreads to all connected land horizontally and vertically. By the time the paint stops spreading, the entire island is colored red (or in our code, changed to '0'). As you continue reading the map, you will never double-count this island because it no longer looks like unvisited land.

The brute force, and where it wastes work ​

A naive brute force idea might be to find all '1's and try to group them into sets by repeatedly checking if any '1' is next to a known set, merging sets when they touch. Why is this too slow? If you have N total land cells, repeatedly scanning to merge adjacencies could take O(N^2) time in the worst case (imagine a long snake-like island where you discover the connections one by one). It wastes an immense amount of time re-evaluating the same boundaries. The flood-fill optimally eliminates this waste by exhaustively consuming an entire island the moment it is found, ensuring every cell is processed exactly once.

The solution ​

python
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:  # (1)
            return 0
        rows, cols = len(grid), len(grid[0])  # (2)

        def sink(r: int, c: int):  # (3)
            if r < 0 or r >= rows or c < 0 or c >= cols:  # (4)
                return
            if grid[r][c] != '1':  # (5)
                return                       # water, or already sunk
            grid[r][c] = '0'                 # (6) mark BEFORE recursing
            sink(r + 1, c)  # (7)
            sink(r - 1, c)
            sink(r, c + 1)
            sink(r, c - 1)

        count = 0  # (8)
        for r in range(rows):  # (9)
            for c in range(cols):
                if grid[r][c] == '1':        # (10) a new island
                    count += 1  # (11)
                    sink(r, c)  # (12)

        return count
ts
function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;  // (1)
  const rows = grid.length, cols = grid[0].length;  // (2)

  function sink(r: number, c: number): void {  // (3)
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;  // (4)
    if (grid[r][c] !== '1') return;  // (5)
    grid[r][c] = '0';  // (6)
    sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1);  // (7)
  }

  let count = 0;  // (8)
  for (let r = 0; r < rows; r++)  // (9)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === '1') { count++; sink(r, c); }  // (10)

  return count;
}

Mark before recursing. Setting grid[r][c] = '0' before the four calls is what stops the search coming straight back to this cell and looping forever.

Never restore it. A cell belongs to exactly one island; putting the '1' back would recount it. This is the point where backtracking habits go wrong — compare 4.18.6 Word Search, where the restore is mandatory because you are finding paths, not regions.

The grid is the visited set. No extra structure needed. If you must not modify the input, keep a separate visited array of the same shape — same algorithm, O(rows × cols) extra space.

Line by line ​

(1) An empty grid has no islands.

(2) The grid's size, for the edge checks.

(3) sink(r, c) wipes out the whole island that contains cell (r, c), turning every connected land cell into water. Each island is then counted once and never again.

(4) Off the grid, so stop.

(5) Water, or land that was already sunk, so stop. This one check is both "is it land?" and "have I visited it?", because sinking a cell turns it into water.

(6) Sink this cell before visiting its neighbours. This order is essential. If the neighbours were visited first, cell (0, 0) would visit (1, 0), which would visit (0, 0) again, forever.

(7) Spread to the four neighbours: down, up, right, left. Each call sinks that neighbour's part of the island.

(8) The island counter.

(9) Look at every cell.

(10) Land that has not been sunk yet must belong to a new island. Every earlier island was sunk completely, so this cell cannot be part of one.

(11) Count the new island, and

(12) sink all of it, so none of its other cells is counted again.

Trace ​

Let's trace a small 2x2 grid:

1 0
1 1
StepActionState / Recursion
1Outer loops start at (r=0, c=0)grid[0][0] is '1'. count becomes 1. Call sink(0, 0).
2sink(0, 0) executesMarks grid[0][0] = '0'. Grid is now [[0, 0], [1, 1]]. Recurse to neighbors.
3sink calls on neighborssink(1, 0) is called. (Others go out of bounds or hit '0').
4sink(1, 0) executesMarks grid[1][0] = '0'. Grid is now [[0, 0], [0, 1]]. Recurse to neighbors.
5sink(1, 1) executesMarks grid[1][1] = '0'. Grid is now [[0, 0], [0, 0]]. All connected components are sunk.
6Outer loops continuer=0, c=1 is '0'. r=1, c=0 is '0'. r=1, c=1 is '0'. No more '1's found.
7EndReturns count = 1.

Edge cases ​

  • No land at all. The count stays 0.
  • The whole grid is land. One island.
  • Diagonal neighbours. They do not join islands. Only up, down, left and right count.
  • A very large island. The recursion can be as deep as the island has cells. Python stops at about 1,000 nested calls by default, so a 300 × 300 island would crash it. The breadth-first version below avoids that.

The BFS version, and when you need it ​

DFS recursion depth can reach rows × cols. On a 1000×1000 grid that is a million stack frames, which overflows in Python (default limit around 1000) and in most languages.

BFS has no recursion at all:

python
from collections import deque

def bfs(r, c):
    queue = deque([(r, c)])
    grid[r][c] = '0'                                  # mark on ENQUEUE
    while queue:
        cr, cc = queue.popleft()
        for nr, nc in ((cr+1,cc), (cr-1,cc), (cr,cc+1), (cr,cc-1)):
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                grid[nr][nc] = '0'                    # mark BEFORE enqueueing
                queue.append((nr, nc))

Marking on enqueue, not on dequeue, is essential. If you mark when you take a cell out, the same cell can be added several times before it is ever processed, and the queue grows far beyond the grid size.

Both are O(rows × cols). Use DFS for brevity, BFS when the grid is large.

Complexity ​

O(rows \times cols) time — every cell is examined a constant number of times, because once sunk it is never entered again. To break it down like you're talking to a friend: "We iterate through the entire grid once with our nested loops. That takes O(rows \times cols). When we find an island, our DFS visits its cells. But because we mutate the cell to '0' immediately, we will never process that cell again inside another DFS, and our outer loop will just skip over it. Therefore, each cell is processed at most a small, constant number of times."

Space is O(rows \times cols) in the worst case, for the recursion stack or the queue, when the grid is one giant island. In that scenario, a DFS trace snakes through every single cell before hitting a dead end, accumulating rows \times cols frames on the call stack. For BFS, the queue holds at most the perimeter of the expanding search, which is bounded by O(\min(rows, cols)), but the theoretical worst-case space bound usually simplifies to the same total dimensions depending on grid shapes.

Where this goes next ​

Eight problems in this chapter are this flood fill with one thing changed:

problemchange
Max Area of Islandthe flood returns a count instead of nothing — 4.20.3
Surrounded Regionsflood from the border to mark survivors — 4.20.5
Pacific Atlanticflood from two edge sets and intersect — 4.20.4
Number of Distinct Islandsrecord each island's shape as a fingerprint
Number of Closed Islandsflood the border first, then count what remains
Number of Provincesthe same on an adjacency matrix instead of a grid
Flood Fill (LeetCode 733)the same, changing colours

Union-find also solves this: union each land cell with its land neighbours, and count the components. It is O(rows \times cols \times \alpha) and more code. It earns its place only when land cells are added over time and you must report the count after each addition — that is "Number of Islands II", and it is the version where DFS would have to re-scan everything after every addition.

What the interviewer will push on ​

"Why does counting from an unvisited cell work?" Every island is entered exactly once, from whichever of its cells the scan meets first.

"Do you restore the grid?" No. Regions are not paths.

"What if you cannot modify the input?" A separate visited array.

"What about stack overflow?" BFS, or an explicit stack. Give the million-frame figure.

"What if land is added one cell at a time?" Union-find, because a fresh flood fill after every addition is O(n) each time.

One thing to volunteer: say that the grid is the visited set and that you are deliberately not restoring it. Naming the difference from backtracking shows you know both patterns rather than one habit.

Next: 4.20.2 Clone Graph — a traversal that builds something as it goes.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet