200. Number of Islands

Matrix, DFS, BFS, Union find

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

\

My solution

class Solution:
    # Helper: utilize dfs on land grid[i][j]
    def dfs(self, grid: List[List[str]], i: int, j: int, island: List[Tuple]):
        if (i+1) < len(grid) and grid[i+1][j] == "1" and (i+1, j) not in island:
            island.add((i+1, j))
            self.dfs(grid, (i+1), j, island)
        if (i-1) >= 0 and grid[i-1][j] == "1" and (i-1, j) not in island:
            island.add((i-1, j))
            self.dfs(grid, (i-1), j, island)
        if (j+1) < len(grid[0]) and grid[i][j+1] == "1" and (i, j+1) not in island:
            island.add((i, j+1))
            self.dfs(grid, i, j+1, island)
        if (j-1) >= 0 and grid[i][j-1] == "1" and (i, j-1) not in island:
            island.add((i, j-1))
            self.dfs(grid, i, j-1, island)

    def numIslands(self, grid: List[List[str]]) -> int:
        island = set()
        k = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1" and (i, j) not in island:
                    island.add((i, j))
                    self.dfs(grid, i, j, island)
                    k += 1
        return k

Problem:

• At first, I forget the boardline should be (i-1) ≥ 0/(j-1) ≥ 0, I simply wrote (i-1) > 0, which will ignore the axis with i = 0 or j = 0
• At first, I let island to be a list, however, in this case, if island is a set, the program could be much faster, for list we use append() , but for set, we use add()
• For recurrsion, we should set up the exit condition, like whether the point is out of range et. al.
• Should ask whether could we modify the grid itself, which can be much easier for this kind of problem

\

Solution

class Solution:
		def numIslands(self, grid):
				if not grid:
						return 0
						
				count = 0
				for i in range(grid):
						for j in range(grid[0]):
								if grid[i][j] == "1":
										self.dfs(grid, i, j)
										count += 1
				return count
		
		def dfs(self, grid, i, j):
				# Exit condition
				if i<0 or j<0 or i>=len(grid) or j>len(grid[0]) or grid[i][j] != "1":
						return
				grid[i][j] = "#"
				self.dfs(grid, i-1, j)
				self.dfs(grid, i+1, j)
				self.dfs(grid, i, j-1)
				self.dfs(grid, i, j+1)

if use bfs

from collections import deque
class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        count = 0    
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    self.bfs(grid, i, j, m, n)
                    count += 1
        return count

    def bfs(self, grid, i, j, m, n):
        queue = deque()
        queue.append((i, j))
        grid[i][j] = "#"  # 标记访问过的陆地
        
        while queue:
            x, y = queue.popleft()
            # 四个方向
            for dx, dy in [(1,0), (-1,0), (0,1), (0,-1)]:
                nx, ny = x + dx, y + dy
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                    grid[nx][ny] = "#"
                    queue.append((nx, ny))

Union find

class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.parent = {}
        self.count = 0  # 记录岛屿数
        
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    idx = i * n + j
                    self.parent[idx] = idx
                    self.count += 1  # 每块陆地初始是独立岛屿

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX
            self.count -= 1  # 合并后岛屿数减1

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        uf = UnionFind(grid)
        
        directions = [(1,0), (-1,0), (0,1), (0,-1)]
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    for dx, dy in directions:
                        ni, nj = i + dx, j + dy
                        if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == "1":
                            uf.union(i*n + j, ni*n + nj)
        return uf.count

130. Surround Regions