parikshan

number-of-islands

Difficulty: Medium  ·  Topic: Graphs  ·  Practice it on parikshan: /practice/number-of-islands/start

The story

A satellite-imagery startup gets a binary mask of a coastline: each pixel is land or water. The product team wants to know how many distinct landmasses are visible in the frame. Two pixels are part of the same island if they are land and they touch on a side (up, down, left, right). Diagonal touches do not count. The team will resell the count to insurance underwriters and shipping companies, so the answer has to be exact.

This is the canonical connected components on a grid problem. Every time you see a binary 2-D image and the question is "how many blobs", this is the algorithm. It is also the gateway problem to graphs, because seeing the grid as a graph is the entire shift in thinking.

What's actually being asked

Given an m × n grid of '1's (land) and '0's (water), return the number of islands. Two land cells are in the same island if they share a vertical or horizontal edge.

The naive approach

For each cell, do something. There is no escape from looking at every cell at least once. The question is whether you can visit each one a constant number of times. Yes: a graph traversal does it.

The key insight

Each cell is a node. Each pair of adjacent land cells is an edge. The number of islands is the number of connected components in that graph. To count components, walk through all cells; every time you encounter a land cell that has not been visited, increment the count and run a BFS or DFS from it to mark all the land cells reachable from it as visited.

Two flavours, both equally good:

  • DFS (recursion or explicit stack): natural for "explore everything reachable".
  • BFS (queue): same result; useful when you also care about distance.

Both visit each cell once, so both are O(m·n).

The "marking visited" can be done with a separate visited matrix, or by mutating the grid in place (overwrite land with water). In-place is O(1) extra space; if the spec forbids mutation, use a matrix.

Step-by-step approach

  1. Initialise count = 0.
  2. For each cell (r, c):
    • If grid[r][c] == '1':
      • count += 1.
      • DFS from (r, c): turn it into '0', recurse on the four neighbours that are in bounds and equal '1'.
  3. Return count.

The DFS:

def dfs(r, c):
    if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != '1':
        return
    grid[r][c] = '0'
    dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

Worked example

grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
  • Outer loop reaches (0,0): it is '1', count=1. DFS turns the entire top-left 2×2 block to '0'.
  • Outer loop reaches (2,2): it is '1', count=2. DFS turns it to '0'.
  • Outer loop reaches (3,3): it is '1', count=3. DFS turns (3,3) and (3,4) to '0'.
  • No more '1's. Return 3.

Complexity

  • Time: O(m · n). Every cell is visited a constant number of times.
  • Space: O(m · n) worst case for the recursion stack on a giant single island. For very large grids, switch to an explicit stack (iterative DFS) to avoid Python's recursion limit.

Common pitfalls

  • Forgetting to mark visited: infinite loop, then a stack overflow. Always mark before recursing on neighbours.
  • Allowing diagonals: re-read the spec. If diagonals count, the algorithm is the same but the four neighbours become eight.
  • Comparing the cell to 1 instead of '1': most LeetCode-style problems use string characters, not integers. Type errors fail silently on Python.
  • Mutating a grid that the caller still owns: if the spec says "don't modify input", use a visited matrix. Otherwise, mutate; it is the simplest.
  • Hitting Python's recursion limit: a grid that is one giant snake-shaped island can blow the stack at 1000+ cells. Either sys.setrecursionlimit (Python) or rewrite DFS with an explicit deque.

Where this shows up in the enterprise

  • Satellite and aerial imagery (Planet Labs, Mapbox, Maxar): counting buildings, fields, vehicles in segmentation masks.
  • Medical imaging (Siemens Healthineers, GE Healthcare): connected components on CT scans for tumour or organ segmentation.
  • Photoshop and Lightroom magic-wand selection: literal flood-fill on pixels.
  • Game maps: counting reachable regions in a level editor.
  • Industrial defect detection (Cognex, Keyence cameras): counting separate defects on a chip wafer.
  • Cloudflare attack-traffic clustering: connected components in an IP-source × time grid identify a botnet's footprint.
  • Operations research / facility location: counting clusters of demand points.
  • Networking topology: counting subnets that are connected through specific links.
  • Genomics: connected regions on a methylation map.
  • Disaster response (NASA AID, Red Cross): post-storm satellite imagery to count separate flooded regions for insurance and triage.

The grid in your problem is rarely a tile map; it is more often a mask over a real-world image. The algorithm is the same.

Variants you'll see elsewhere

  • max-area-of-island: same template; return the size of the largest island.
  • flood-fill: a single recolouring, same recursion.
  • surrounded-regions: invert the problem; mark the islands that touch the border, then flip the rest.
  • pacific-atlantic-water-flow: two BFS / DFS passes from each ocean's border.
  • rotting-oranges: multi-source BFS; all rotten cells start in the queue together.
  • clone-graph: not on a grid, but the same DFS-with-memo pattern.
  • word-ladder: BFS over an implicit graph where nodes are strings.

Mastering this one unlocks all of the above with minor edits.

How parikshan turns this into a learning loop

This is the first problem in the bank where the AI training assistant earns its keep. Once you've struggled with the grid-as-graph mental shift, hit /api/training/improve with the Explain intent and ask for the BFS variant. You'll find that the code is structurally identical to your DFS, just with a queue instead of a stack. That equivalence is the moment graphs click.

In parikshan's loop:

  1. Practice mode first. Get it working with DFS. Watch out for the recursion-limit trap on stress tests.
  2. AI training: Explain the BFS version. Internalise the equivalence.
  3. Exam mode, dynamic tests on. Now do max-area-of-island and flood-fill without help. Both should take under five minutes.

The proctor on exam mode flags external paste and external help, so you can be honest about which problems you've actually internalised vs. which you've outsourced. That honesty is the loop's product.

In the AI-integrated workspace

In production, your agent will write grid-traversal code more than almost any other algorithm class. Image-pipeline microservices, dashboard heatmaps, occupancy detection, geofence analytics, all of it.

What your review must check:

  1. The right neighbour set: four-connectivity or eight-connectivity? The agent will not raise the question; you must.
  2. The recursion safety: for grids larger than a few thousand cells, the agent's DFS will stack-overflow. Either an explicit stack or BFS is required.
  3. The in-place vs. copy decision: a feature flag turns this into a security boundary (do not mutate inputs you don't own). The agent will not flag the trade-off.
  4. The off-by-one in bounds checking: r < m and c < n are easy to get inverted with r <= m. Generated code routinely fails on the last row.

Engineers who can audit grid traversals in 30 seconds are the ones who ship correct image-pipeline code. The 30-second audit is the entire skill, and number-of-islands is where you learn it.