200. Number of Islands
- Total Accepted: 71131
- Total Submissions: 228449
- Difficulty: Medium
- Contributors: Admin
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.
Example 1:
11110 11010 11000 00000
Answer: 1
Example 2:
11000 11000 00100 00011
Answer: 3
Code
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
if not grid:
return 0
res = 0
for i in xrange(len(grid)):
for j in xrange(len(grid[0])):
if grid[i][j] == '1':
res += 1
self.explore(grid, i, j)
return res
def explore(self, grid, i, j):
grid[i][j] = "*"
# down, up, right, left
for di, dj in ((0, 1), (0, -1), (1, 0), (-1, 0)):
if 0 <= i+di < len(grid) and 0 <= j+dj < len(grid[0]) \
and grid[i+di][j+dj] == '1':
self.explore(grid, i+di, j+dj)
Idea
Whenever you see an 1, increment result by 1. The method explore visits adjacent 1’s in a DFS manner. Every visited cell will be re-marked so that no future visit will happen.
If the grid size is N^2, then the time complexity is O(N^2) and the space complexity is O(N^2) as well because DFS recursive calls can visit up to all cells and take O(N^2) stack frame.
Reference: https://discuss.leetcode.com/topic/11590/simple-java-solution