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) 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
Accepted O(MN) Solution: linear time to the number of elements in the grid
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.