Leetcode 200. Number of Islands (Python)

Related Topic

Depth-First-Search.

Description

Given a 2d grid map of ‘1’s (land) and ‘0’s (water), count 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.

Sample I/O

Example 1

Input:
11110
11010
11000
00000

Output: 1

Example 2

Input:
11000
11000
00100
00011

Output: 3

Note:

• 1 <= d, f <= 30
• 1 <= target <= 1000

Methodology

This question can be solved by Depth First Search and it is very classic DFS question for list.

To find the number of islands, we need to move from left top to bottom right. For each move we can go up or right or down or left directions. After each move, if we are out of the bondary or we find water or we repeat the path then we return to last move and change to another direction to move until we find 1 island. After we find island, we update the count and start to find another island.

Code

def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
        row = len(grid)
        col = len(grid[0])
        visited = set()
        count = 0
        directions=[(-1,0),(0,1),(1,0),(0,-1)]
        def findIsland(x,y):
            for dx, dy in directions:
                nx,ny = x+dx, y+dy
                if 0<=nx<row and 0<=ny<col and grid[nx][ny]=='1' and (nx,ny) not in visited:
                    visited.add((nx,ny))
                    findIsland(nx,ny)
            
        for x in range(row):
            for y in range(col):
                if grid[x][y] == '1' and (x,y) not in visited:
                    count +=1
                    visited.add((x,y))
                    findIsland(x,y)         
        return count

BigO

We iterate each cell will cost O(m*n) where m*n is the size of the 2D list. Each cell will have four directions, the total O(4*m*n)