# Accepted O(MN) Solution: linear time to the number of elements in the grid

• ``````class Solution:
# @param grid, a list of list of characters
# @return an integer
def numIslands(self, grid):
# How many connected components?
# Region rowing Starting with a '1', until all its four neighbor have been visited, we finished one island, count += 1
# How to find staring '1's? Keep a hashset set1 to keep all 1s in the first scan,  when visit an island, delete corresponding 1s in the hashset
# How to grow region? Find (r,c)'s four neighbors left/top/right/bottom (r, c-1), (r-1, c), (r, c+1), (r+1, c), remember to check boundray
# Iterate until the set1 is empty
#
# We could either delete the visited 1s from the hash set, or mark it as value 2(integer) or 0(binary)?
#
if not grid: #empty
return 0
R, C = len(grid), len(grid[0])
set1 = set() # hash set
for r in range(R):
for c in range(C):
if grid[r][c] == "1":
set1.add((r,c))
rOffset = [0, -1, 0, 1];
cOffset = [-1, 0, 1, 0];
count = 0 # current label for island, island is marked as 2 for the 1st iland, 3 for the 2nd one, etc.
while set1:
# loop until no 1s left in the hash set
# Find current island connected to (r,c), delete all those elements from set1
count += 1
r, c = set1.pop()
# find all 1s in current island that contains r, c
s = [] # stack
s.append((r,c))
while s:
r, c = s.pop()
# all four nighbors of (r,c)
for i in range(len(rOffset)):
r2, c2 = r + rOffset[i], c + cOffset[i]
if (r2>=0) and (r2<R) and (c2>=0) and (c2<C) and ((r2,c2) in set1):
set1.remove((r2,c2))
s.append((r2,c2))
return count``````

• I used one hashset and one stack.
I believe it can be simplified.
Your suggestions will be highly appreciated.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.