DSA sheet · Graphs · Connected components on a grid

Number of Islands

This is Number of Provinces again, but now the graph is hidden inside a grid. Every land cell is a node, and two land cells touching up/down/left/right are joined by an edge. The teacher's point is that counting islands = counting connected components. She solves it with BFS this time (Provinces was DFS), shows the dr/dc direction trick, and shows how to save memory by marking visited inside the grid itself. This grid-walking template is used in almost every grid problem that follows.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics and grids as graphs
• Part A · Count islands with BFS (the teacher's code)
• Part B · Count islands with DFS
• Part C · Revision page

Part 0 · Graph basics and grids as graphs

Nodes, edges, and the kinds of graphs

A graph is a set of nodes (points) joined by edges (lines). An edge can be undirected (usable both ways, drawn (a)—(b)) or directed (one way, drawn (a)→(b)). It can also carry a number, a weight (drawn (a)—7—(b)). This problem's graph is undirected and unweighted.

Input forms and the adjacency list

Normal graph problems give an edge list ([[0,1],[1,2]]), an adjacency matrix (n × n of 0/1) or an adjacency list (adj[u] = neighbours of u). Usually we turn the input into an adjacency list first:

n = 4
edges = [[0, 1], [1, 2], [2, 3]]
adj = [[] for _ in range(n)]
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)      # leave this line out for a directed graph
print(adj)                # [[1], [0, 2], [1, 3], [2]]

Visited and connected components

In a graph you can walk in circles (a → b → a …). So every traversal keeps a visited record: mark a node when you reach it, and never enter a marked node again. A connected component is a group of nodes that can all reach each other, with no edge leaving the group. "Start a traversal from every unvisited node and count the starts" counts the components. That was the whole idea of Number of Provinces.

BFS and DFS

BFS (breadth first search) uses a queue: take the oldest node, add its unvisited neighbours to the back. It spreads out in rings, layer by layer. DFS (depth first search) uses recursion or a stack: dive into one neighbour as deep as possible, then come back. For counting components either works, because both reach every node connected to the start.

Grids as graphs

A grid with m rows and n columns is a graph in disguise:

• each cell (r, c) is a node;
• its neighbours are the 4 cells around it: up (r-1, c), left (r, c-1), down (r+1, c), right (r, c+1);
• we never build an adjacency list: the neighbours are computed on the spot.

            (r-1, c)
               ↑
 (r, c-1)  ←  (r, c)  →  (r, c+1)
               ↓
            (r+1, c)

The dr/dc trick. Instead of writing 4 near-identical blocks, store the 4 moves as two small lists: dr (change in row) and dc (change in column). Pair number i is (dr[i], dc[i]), and the neighbour is (r + dr[i], c + dc[i]).

Bounds check. A neighbour of an edge cell can fall outside the grid (row −1, or column n). Always check 0 <= nr < m and 0 <= nc < n before reading grid[nr][nc]. In Python, grid[-1] doesn't even crash: it silently reads the last row, which gives wrong answers. So this check is essential.

Marking visited in place. Instead of a separate visited grid, you can overwrite a cell (for example, land → water) once you've reached it. We'll see exactly why that's safe in Part A.

grid = ["110",
        "011"]
m, n = len(grid), len(grid[0])
dr = [-1, 0, 1, 0]       # up, left, down, right
dc = [0, -1, 0, 1]
r, c = 0, 1
for i in range(4):
    nr, nc = r + dr[i], c + dc[i]
    if 0 <= nr < m and 0 <= nc < n:
        print((nr, nc), grid[nr][nc])
# prints (0, 0) 1, then (1, 1) 1, then (0, 2) 0   (up is outside, so skipped)

Part A · Count islands with BFS

LeetCode 200

1The question in simple words

You get an m × n grid of '1' (land) and '0' (water). An island is a group of land cells joined horizontally or vertically (left, right, up, down). Diagonal touching does not join cells. Everything outside the grid counts as water. Return how many islands there are.

     c: 0 1 2 3 4
 r=0    1 1 0 0 0
 r=1    1 1 0 0 0
 r=2    0 0 1 0 0
 r=3    0 0 0 1 1

        A A . . .
        A A . . .
        . . B . .
        . . . C C
   3 islands: A, B, C

Notice that B and C touch only at a corner (diagonally): (2,2) and (3,3). That does not join them, so they are 2 separate islands.

2What the constraints tell us

• 1 ≤ m, n ≤ 300 → at most 90,000 cells. Visiting each cell a few times is tiny, so an O(m·n) solution is what we want, and it's easily fast enough.
• Cells are the characters '1' and '0', not the numbers 1 and 0. In Python, '1' == 1 is False! Compare with '1'.
• All 4 outer edges are surrounded by water → we never have to think about land "continuing" outside. Just don't step outside.
• A grid can be 300 × 300 and all land. A recursive DFS would then go up to 90,000 calls deep, far past Python's default limit of 1000. That is one more reason BFS is a good choice in Python (more in Part B).

3Intuition: how to think about it

Walk over the map row by row. The moment your foot lands on a piece of land you haven't explored yet, you've found a new island, so count it. Then, before moving on, explore that whole island and mark every one of its cells, so you'll never count it again when your scan reaches those cells later.

The teacher's observation: this is word-for-word the Number of Provinces idea. Provinces asked for groups of connected cities. Here we want groups of connected land cells. Same pattern: outer loop over all nodes + one traversal per unvisited node + count the traversals.

4Building the logic from the teacher's example

Step 1: where can we move from a land cell?

Start at (0,0). Up and left are outside the grid. Down (1,0) is land, and right (0,1) is land. From there we also reach (1,1). The island stops wherever there is a 0, because water can never be part of an island. And we never step diagonally, because the question only allows horizontal and vertical joins.

Step 2: start only from land

A traversal from a water cell would explore nothing, and it is not an island. So the outer loop starts a BFS only on a land cell that hasn't been visited. Every such start is a new island → count it.

Step 3: why mark visited at all?

(0,0)'s child is (1,0). But (1,0)'s children include (0,0) again! Without marking, we would push (0,0) again, then (1,0) again… an endless loop. Marking a cell as soon as we reach it stops this.

Step 4: the "visited inside the grid" trick (the 10% case)

The teacher says that in most graph problems (about 90%) you need a separate visited array, but sometimes (the other 10%) the input itself can remember what you visited. Her reasoning goes like this:

• We never step onto water ('0'), because the bounds-and-land check rejects it.
• "Visited" also means never step here again.
• So the two mean the same thing for our walk! Once we explore a land cell, we can turn it into water ('0'). From then on the normal land check already refuses to enter it.

This saves a whole m × n visited grid. But it changes the input. The teacher's advice: do it only if the interviewer allows it, or else keep a separate visited grid (O(m·n) extra space).

Step 5: BFS: mark when you push, not when you pop

BFS starts by putting (r, c) in a queue and immediately marking it '0'. Then, while the queue isn't empty: pop a cell, try its 4 directions, and for each valid land neighbour, push it and mark it '0' right away. The teacher's reason: the start cell was marked at the moment it entered the queue, so follow the same rule for every cell. Marking on push means a cell can never be pushed twice by two different neighbours.

Step 6: the direction order the teacher uses

dr = [-1, 0, 1, 0], dc = [0, -1, 0, 1]. Read them as pairs: (−1, 0) = up, (0, −1) = left, (1, 0) = down, (0, 1) = right. The teacher mentions the alternative is to write 4 separate calls/blocks with r-1, c / r+1, c / r, c-1 / r, c+1. The arrays just let one small loop do all four. The order doesn't change the answer, only the visiting order.

5Approach steps

1. m = len(grid), n = len(grid[0]), islands = 0.
2. For every cell (i, j): if grid[i][j] == '1' → bfs(i, j), then islands += 1.
3. bfs(r, c): push (r, c), set it to '0'.
4. While the queue isn't empty: pop (r, c). For each of the 4 directions compute (nr, nc). If it is inside the grid and equal to '1': push it and set it to '0'.
5. Return islands.

6Code (Python)

from collections import deque

class Solution:
    def numIslands(self, grid):
        m, n = len(grid), len(grid[0])
        islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':          # unexplored land = a new island
                    self.bfs(grid, i, j)
                    islands += 1
        return islands

    def bfs(self, grid, r, c):
        m, n = len(grid), len(grid[0])         # sizes again (not known in here)
        dr = [-1, 0, 1, 0]                     # up, left, down, right
        dc = [0, -1, 0, 1]
        queue = deque()
        queue.append((r, c))
        grid[r][c] = '0'                       # visited = turned into water
        while queue:
            r, c = queue.popleft()
            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]
                if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
                    queue.append((nr, nc))
                    grid[nr][nc] = '0'         # mark when pushed

LeetCode passes grid as a list of lists of characters, so grid[r][c] = '0' works. (A list of plain strings can't be changed in place. The test snippet below converts strings to lists first.)

7Code line by line

8Dry run on the teacher's grid

Directions are tried in the order up, left, down, right. "✗out" = outside the grid, "✗0" = water or already marked.

Step 4 shows why marking on push matters: (1,1) was pushed by (1,0) and is already '0', so (0,1) does not push it a second time.

x x 0 0 0
x x 0 0 0
0 0 1 0 0
0 0 0 1 1     islands = 1

x x 0 0 0
x x 0 0 0
0 0 x 0 0
0 0 0 1 1     islands = 2

x x 0 0 0
x x 0 0 0
0 0 x 0 0
0 0 0 x x     islands = 3

9Complexity & remember

• Time O(m·n). The teacher's reasoning: the two outer loops visit m·n cells. A BFS is started only once per island, never for an already-sunk cell. Across all BFS calls together, each land cell is pushed and popped once (in her example: 4 cells, then 1, then 2). Even in the worst case, all land, the first BFS sinks all m·n cells and the scan never starts another one. Each pop tries 4 directions, so it's 4·m·n, and the constant 4 is dropped → O(m·n).
• Space O(m·n) in the worst case for the queue (she says "nearly m·n", a safe upper bound; in practice the BFS front is much smaller than the whole grid). No visited grid is needed, thanks to the in-place marking. With a separate visited grid you'd add another O(m·n).

Part B · Count islands with DFS

The teacher asks us to submit this question both ways, so that "reaching a node's children" becomes second nature. With DFS, everything is the same except how one island is explored.

1The question

Same as Part A.

2Constraints, and a Python warning

Same constraints. But a recursive DFS on a 300 × 300 grid of all land can go 90,000 calls deep. Python stops at about 1000 by default (RecursionError). Two fixes: raise the limit with sys.setrecursionlimit (fine on LeetCode, risky elsewhere), or use an explicit stack, which has no depth limit. Both are shown below.

3Intuition

From a land cell, sink it, then dive into its first land neighbour, then that one's first land neighbour, and so on. Only when you're stuck do you come back and try the next direction. It's the same island, sunk in a different order.

4What changes from BFS

• The teacher's "4 calls" form: dfs(r-1, c), dfs(r+1, c), dfs(r, c-1), dfs(r, c+1). With recursion it's simplest to check bounds and land at the top of the call (the base case), then make the 4 calls blindly.
• The explicit stack form is the BFS code with popleft() changed to pop() (take the newest instead of the oldest).

5Approach steps

1. Same outer scan and count as Part A.
2. dfs(r, c): if outside the grid or not '1' → return.
3. Set grid[r][c] = '0', then call dfs on up, down, left, right.

6Code (Python)

import sys

class Solution:
    def numIslands(self, grid):
        sys.setrecursionlimit(10**6)           # deep islands need deep recursion
        m, n = len(grid), len(grid[0])
        islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    islands += 1
        return islands

    def dfs(self, grid, r, c):
        if r < 0 or r >= len(grid) or c < 0 or c >= len(grid[0]):
            return                             # stepped outside
        if grid[r][c] != '1':
            return                             # water or already sunk
        grid[r][c] = '0'                       # mark first
        self.dfs(grid, r - 1, c)               # up
        self.dfs(grid, r + 1, c)               # down
        self.dfs(grid, r, c - 1)               # left
        self.dfs(grid, r, c + 1)               # right

class Solution:
    def numIslands(self, grid):
        m, n = len(grid), len(grid[0])
        dr = [-1, 0, 1, 0]
        dc = [0, -1, 0, 1]
        islands = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] != '1':
                    continue
                islands += 1
                stack = [(i, j)]
                grid[i][j] = '0'
                while stack:
                    r, c = stack.pop()             # newest first = depth first
                    for d in range(4):
                        nr, nc = r + dr[d], c + dc[d]
                        if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == '1':
                            grid[nr][nc] = '0'
                            stack.append((nr, nc))
        return islands

7Code line by line (recursive version)

8Dry run: island A with recursive DFS

1. dfs(0,0): land → sink. Call up (−1,0): outside → return.
2. Call down dfs(1,0): land → sink. Its up (0,0) is now '0' → return. Its down (2,0) is water → return. Its left is outside. Its right dfs(1,1): land → sink.
3. Inside dfs(1,1): up dfs(0,1): land → sink. All of (0,1)'s neighbours are '0' or outside → it returns.
4. dfs(1,1)'s other directions are water/sunk → return. Back in (1,0) → return. Back in (0,0): left is outside, and right (0,1) is already '0' → return.
5. Island A is fully sunk with one top-level call → islands = 1. B and C go the same way → 3.

9Complexity & remember

• Time O(m·n): each cell is sunk once, and each sunk cell makes 4 cheap calls/checks.
• Space O(m·n) in the worst case: the recursion (or stack) can hold a whole snake-shaped island.

Part C · Revision page

def make(rows):
    return [list(row) for row in rows]     # LeetCode gives lists of characters

s = Solution()
print(s.numIslands(make(["11000", "11000", "00100", "00011"])))   # 3
print(s.numIslands(make(["11110", "11010", "11000", "00000"])))   # 1
print(s.numIslands(make(["000", "000"])))                         # 0
print(s.numIslands(make(["1"])))                                  # 1
print(s.numIslands(make(["101", "010", "101"])))                  # 5

Based on this video: Number of Islands | Graph