200. Number of Islands

https://leetcode.com/problems/number-of-islands/description/

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

BFS Approach

Initialize a deque to use as a queue. For every grid[i][j], initiate bfs if it is 1.
Mark the visited grid[i][j] by flipping the '1' value to 0.
When every possible path starting from land is searched, increment the number of island count

from collections import deque
class Solution:
    def numIslands(self, grid):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    grid[i][j] = 0 # Mark as visited
                    self.bfs(grid, i, j) # turn the adjancent '1' to '0'
                    count += 1
        return count

    def bfs(self,grid, i, j):
        queue = deque([])
        queue.append((i,j))
        while queue:
            qr, qc = queue.popleft()
            directions = [[1,0],[-1,0],[0,1],[0,-1]]
            for dr, dc in directions:
                nr, nc = qr + dr, qc + dc
                if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '1':
                    queue.append((nr,nc))
                    grid[nr][nc] = 0 # Mark as visited

N: number of elements, M: length of each elements

Time Complexity: O(N*M) Visiting every elements in the grid at most once
Space Complexity: O(N*M) Queue size

DFS Approach

Difference with BFS would be the order of search

from collections import deque
class Solution:
    def numIslands(self, grid):
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j) # turn the adjancent '1' to '0'
                    count += 1
        return count

    def dfs(self, grid, i, j):
        grid[i][j] = 0 # Mark as visited
        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        for dr, dc in directions:
            nr, nc = i + dr, j + dc
            if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == '1':
                self.dfs(grid, nr, nc)

N: number of elements, M: length of each elements -Time Complexity: O(N*M) Visiting every elements in the grid at most once -Space Complexity: O(1) No extra memory used

sophryu99 / algorithm

200. Number of Islands #22

200. Number of Islands