Number of Islands
Table of Contents + −
This one looks scary at first. You see a grid full of 1s and 0s and you panic. But relax. The interviewer is not testing the grid. They want to see if you can spot a graph hiding inside a grid. Each piece of land is just a node. The lands next to it are its neighbours. So the real question is simple. Can you walk through connected things and count the separate groups?
🏝️ The Problem
You get a grid. A 1 means land. A 0 means water. Land cells that touch each other up, down, left, or right are part of the same island. Land cells touching only on the corners do not count. Your job is to count how many separate islands there are.
Input:1 1 0 0 01 1 0 0 00 0 1 0 00 0 0 1 1
Output: 3See, the top-left block of four 1s is one island. The single 1 in the middle is another. The two 1s at the bottom right touch side by side, so they are the third. That gives us 3.
🤔 How do you even start?
The simple idea most people say first is this. “I will count every land cell.” But that is wrong, right? A single island can have many land cells. Counting cells gives you the wrong answer. We do not want the number of land cells. We want the number of connected groups of land.
So here is the trick. The moment you find a piece of land you have not seen before, that is a brand-new island. You add one to your count. Then you must walk to every land cell connected to it and mark it as visited. That way you never count the same island twice.
That walking-and-marking idea has a name. It is called flood fill. Think of spilling a bucket of paint on one land cell. The paint spreads to every connected land cell and stops at water. Whatever the paint touches is one island.
🌊 The flood-fill idea
Imagine Riya pours blue paint on one cell of land. The paint flows to the cell above, below, left, and right. But only if that cell is also land. From each new land cell the paint keeps flowing the same way. It stops at water and at the edge of the grid. When the paint cannot spread any more, one full island is painted. We do this spreading with DFS (Depth-First Search). That means we go deep into one direction first before coming back.
The neat part is this. Once a cell is painted, we change it to 0. That way we never visit it again, and we do not need a separate visited grid.
🪜 Steps to count the islands
- Set a counter
islandsto 0. - Go through every cell in the grid, row by row.
- If the cell is water (
0), skip it. - If the cell is land (
1), you found a new island. Add 1 toislands. - Run DFS from that cell. Sink it by turning it into
0, then do the same for its up, down, left, and right neighbours that are land. - After scanning the whole grid,
islandsholds the answer.
💻 The Code
Here we run DFS from each unvisited land cell, sink the whole island, and count one island each time.
def num_islands(grid): rows, cols = len(grid), len(grid[0])
# Sink the whole island starting from (r, c) def dfs(r, c): # Stop if we go off the grid or hit water if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0: return grid[r][c] = 0 # mark this land as visited dfs(r - 1, c) # up dfs(r + 1, c) # down dfs(r, c - 1) # left dfs(r, c + 1) # right
islands = 0 for r in range(rows): for c in range(cols): if grid[r][c] == 1: # new island found islands += 1 dfs(r, c) # sink it return islands
grid = [ [1, 1, 0, 0, 0], [1, 1, 0, 0, 0], [0, 0, 1, 0, 0], [0, 0, 0, 1, 1],]print("Number of islands:", num_islands(grid))The output of the above code will be:
Number of islands: 3⏱️ Time and Space Complexity
Let rows be the number of rows and cols be the number of columns. So the grid has rows * cols cells in total.
| Approach | Time | Space | Why |
|---|---|---|---|
| Count land cells (wrong) | O(rows * cols) | O(1) | Fast, but gives the wrong answer |
| DFS flood fill | O(rows * cols) | O(rows * cols) | Each cell is visited once; recursion stack can grow as big as the grid |
We touch every cell at most one time. That is why the time is O(rows * cols). The space comes from the recursion calls. In the worst case the whole grid is land, so the call stack can hold as many cells as the grid has.
Tip
Marking a visited land cell as 0 saves you from building a separate visited grid. If the interviewer says you are not allowed to change the input, just keep a separate visited table of the same size and check it instead.
🧩 Key Takeaways
- ✅ A grid problem is often a graph problem. Each land cell is a node, and its up/down/left/right land cells are its neighbours.
- ✅ You count one island the moment you find new land, then flood fill to sink the rest of it so you never count it again.
- ✅ Flood fill just means spreading to all connected land cells, the way paint spreads.
- ✅ Sinking land to
0is a clean way to mark cells visited without extra memory. - ✅ The time is O(rows * cols) because every cell is touched only once.
Check Your Knowledge
Test what you learned. Pick an answer for each question, then click Check.
- 1
Why is counting all the land cells the wrong way to solve this problem?
Why: A single island is made of many connected land cells, so counting cells gives more than the number of islands.
- 2
When does the DFS (flood fill) stop spreading?
Why: The DFS returns as soon as it goes out of bounds or lands on a water cell (0).
- 3
Why do we set a visited land cell to 0 during the flood fill?
Why: Setting it to 0 marks the cell as visited so we never start a new count from it again.
- 4
What is the time complexity of the DFS flood-fill solution?
Why: Every cell in the grid is visited at most once, so the work is proportional to rows times cols.