0200.Number of Islands

Link: 200. Number of Islands - Medium
Track: NeetCode150

Question

Restate the problem

• We’re given a 2D grid of '1' and '0', where'1' is land and '0' is water.
• An island is a group of land cells connected up/down/left/right.
• Return how many separate islands exist

Edge Case

• empty-grid guard: empty grid, return 0

---

Method	Approach	Time Complexity	Space Complexity
Method 1 ⭐	BFS (visited set)	$O(m\cdot n)$	$O(m\cdot n)$
Method 2	DFS (visited set)	$O(m\cdot n)$	$O(m\cdot n)$
Method 3	BFS (In place)	$O(m\cdot n)$	$O(1)$

Method 1 - BFS (visited set)

Approach

• Scan every cell. If I see a '1' that I haven’t visited, that means I found a new island, so I do res += 1.
• Then I run BFS starting from that cell. I use a queue and expand in four directions. If a neighbor is in bounds, is '1', and hasn’t been visited, I add it to the queue and mark it as visited.
• After BFS finishes, all connected land cells in that island are marked as visited, so I won’t count the same island again.

Complexity

• Time Complexity: O($m\ast n$)
• Space Complexity: O($m\ast n$)

Code

from collections import deque
 
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
		if not grid or not grid[0]:
            return 0
 
        rows, cols = len(grid), len(grid[0])
        visited = set()
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        count = 0
        
        def bfs(r, c):
            queue = deque([(r, c)])
            visited.add((r, c))
            while queue:
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = dr + r, dc + c
                    if (0 <= nr < rows and 0 <= nc < cols) \
                        and grid[nr][nc] == "1" \
                        and (nr, nc) not in visited:
                        queue.append((nr, nc))
                        visited.add((nr, nc))
                    
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    bfs(r, c)
                    count += 1
        
        return count

Method 2 - DFS (visited set)

Complexity

• Time Complexity: O($m\ast n$)
• Space Complexity: O($m\ast n$)

Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
	    if not grid or not grid[0]:  
			return 0
			
        rows, cols = len(grid), len(grid[0])
        visited = set()
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        count = 0
        
        def dfs(r, c):
            visited.add((r, c))
            
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols \
                    and (nr, nc) not in visited \
                    and grid[nr][nc] == "1":
 
                    dfs(nr, nc)
 
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visited:
                    dfs(r, c)
                    count += 1
        
        return count

Method 3 - BFS (In place)

Complexity

• Time Complexity: O($m\ast n$)
• Space Complexity: O($1$)

Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows, cols = len(grid), len(grid[0])
        dirs = ((1, 0), (-1, 0), (0, 1), (0, -1))
        count = 0
        
        def bfs(r, c):
            if not grid or not grid[0]:
                return 0
            queue = deque([(r, c)])
            grid[r][c] = "0"
            while queue:
                r, c = queue.popleft()
                for dr, dc in dirs:
                    nr, nc = dr + r, dc + c
                    if (
                        (0 <= nr < rows and 0 <= nc < cols) and
                        grid[nr][nc] == "1"
                    ):
                        grid[nr][nc] = "0"
                        queue.append((nr, nc))
                    
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1":
                    bfs(r, c)
                    count += 1
        
        return count

---

Mistake

• Use deque([(r, c)]) not deque((r, c))
  • without [], deque enqueues r and c as two separate ints, so popleft() can’t unpack into r, c.