Number of Islands

Q: What is the time complexity of Number of Islands?

O(rows × cols). The scan looks at every square once, and each land square enters the stack or queue once and checks four neighbours. The seen marks and the stack or queue use O(rows × cols) space on a map that is all land.

Q: Should you use BFS or DFS for Number of Islands?

Both are correct in the same time and space, because the count only needs every square of an island marked. BFS with a queue never recurses; DFS is as safe when it uses an explicit stack.

Q: Can you solve Number of Islands with union-find?

Yes. Put every land square in its own set and start the count at the number of land squares. Join each pair of neighbouring land squares, and lower the count by one whenever a join connects two different sets. With path compression the time is close to O(rows × cols).

Q: Can you count islands without a separate seen array?

Yes, if you may change the map: turn each land square into water as soon as you reach it. Many languages cannot change strings in place, so you copy the rows into a grid of characters first, which costs the same space as the seen marks.

MediumGraphs

+10

You get a map as a list of strings of equal length, where '1' is a square of land and '0' is a square of water. Two land squares belong to the same island when they share a side: up, down, left or right. Squares that only meet at a corner are not connected. Return the number of islands.

Function

numIslands(grid: string-array) → integer

gridstring-array: the map, one string per row
Returnsinteger: the number of islands

Constraints

1 ≤ grid.length ≤ 150
1 ≤ grid[i].length ≤ 150
Every row has the same length.
Every character is '0' or '1'.

Examples

Input: grid = ["11000", "11000", "00100", "00011"]
Output: 3
Explanation: The four squares in the top left form one island. The middle square of the third row only touches them at a corner, so it is a second island. The bottom right pair is the third.

Follow-up

Land now appears one square at a time on a map of water. Can you report the number of islands after each new square without scanning the whole map again?

Solution

Treat each land square as a node joined to the land squares beside it: an island is one connected piece. Scan the map, and each time you reach land you have not seen, count a new island and flood fill it, marking every square of it so the scan never counts it again.

Flood fill with an explicit stack (DFS)

Intuition

An unmarked land square cannot belong to an island you already counted, because counting an island marks all of it. So it starts a new island. A stack you manage yourself marks the rest: each square you pop pushes its unmarked land neighbours, and when the stack is empty the whole island is marked.

Your own stack matters because a recursive fill can go 22,500 calls deep on a 150 × 150 map of solid land. Each square is pushed at most once and checks four neighbours, so the time is O(rows × cols). The marks and the stack take O(rows × cols) space when the map is all land.

Algorithm

Create a seen mark for every square and set the count to 0.
Scan every square, skipping water and squares already seen.
On unseen land, add 1 to the count, mark the square and push it on a stack.
While the stack is not empty, pop a square and push each neighbour inside the map that is unseen land, marking it before you push.
Return the count when the scan ends.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            # Land that no island has claimed yet: a new island.
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        # Mark on push, so no square enters the stack twice.
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Flood fill with a queue (BFS)

Intuition

The count works the same way; only the visit order changes. A queue takes squares from the front and adds unmarked land neighbours to the back, so it visits the island in rings: the first square, then every square one step away, then two steps away. Every square is still visited once, in O(rows × cols) time and space.

The ring order gives each square's distance from the start, so the same loop answers shortest path questions on a grid with one extra number per square.

Algorithm

Create a seen mark for every square and set the count to 0.
Scan every square, skipping water and squares already seen.
On unseen land, add 1 to the count, mark the square and put it in an empty queue.
While the queue has squares, take one from the front and add each neighbour inside the map that is unseen land to the back, marking it as you add it.
Return the count when the scan ends.

def numIslands(grid):
    rows, cols = len(grid), len(grid[0])
    seen = [[False] * cols for _ in range(rows)]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1' or seen[r][c]:
                continue
            count += 1
            seen[r][c] = True
            stack = [(r, c)]
            while stack:
                i, j = stack.pop()
                for ni, nj in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
                    if 0 <= ni < rows and 0 <= nj < cols and grid[ni][nj] == '1' and not seen[ni][nj]:
                        seen[ni][nj] = True
                        stack.append((ni, nj))
    return count

Pitfalls and edge cases

Marking a square when you take it out of the stack or queue instead of when you put it in. The same square then goes in several times.
Comparing a square with the number 1 instead of the character '1'. Each row is a string, so each square is a character.
Reading a neighbour before checking 0 ≤ row < rows and 0 ≤ col < cols. A land square on the edge then reads off the map.
Writing the fill recursively. Python stops at 1,000 calls by default, and other languages can overflow the stack on one large island.
Taking the front of a Python list with pop(0), which costs time proportional to the list. Use collections.deque and popleft().

Frequently asked questions4

What is the time complexity of Number of Islands?

O(rows × cols). The scan looks at every square once, and each land square enters the stack or queue once and checks four neighbours. The seen marks and the stack or queue use O(rows × cols) space on a map that is all land.

Should you use BFS or DFS for Number of Islands?

Both are correct in the same time and space, because the count only needs every square of an island marked. BFS with a queue never recurses; DFS is as safe when it uses an explicit stack.

Can you solve Number of Islands with union-find?

Yes. Put every land square in its own set and start the count at the number of land squares. Join each pair of neighbouring land squares, and lower the count by one whenever a join connects two different sets. With path compression the time is close to O(rows × cols).

Can you count islands without a separate seen array?

Yes, if you may change the map: turn each land square into water as soon as you reach it. Many languages cannot change strings in place, so you copy the rows into a grid of characters first, which costs the same space as the seen marks.

def numIslands(grid):
    # Write code here

Test #1

Test #2

Argument

grid = ["11000", "11000", "00100", "00011"]

Expected Output