LT #200: Count Number of Islands

Day: 0
Type: Graphs
Level: Easy
Link: https://leetcode.com/problems/number-of-islands/description/

TL:DR

Algorithm: BFS/DFS
Approach: Run BFS on each element of the grid. Each successful completion will result in algo returning us with an island cluster (and no duplicates as we keep a track with visited nodes using a set).

Solving the problem

1. This can be solved either by BFS or DFS — the approach is to check for all nodes in all directions and track the cluster of all “1”s .

2. Example: assuming we are given the following input —

grid = [
  ["1","1","1","0","0"],
  ["1","1","0","0","0"],
  ["1","0","0","1","1"],
  ["0","0","0","0","1"]
]

Visualizing the islands (blue is water) —

3. Start with creating variables.

visited = set() # keep track of nodes that are already visited to skip running bfs
numberOfIslands = 0 # increment when cluster is found

4. Find total rows and cols of input grid

rows, cols = len(grid), len(grid[0])

5. Run BFS on node if it’s an island and it has not been visited. Increment after it’s completed.

for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r,c) not in visited:
                    bfs(r,c)
                    numberOfIslands += 1
return numberOfIslands

6. Defining the BFS algorithm —

def bfs(r: int, c: int):
            q = deque() # create queue to add nodes of islands
            q.append((r,c)) 
            visited.add((r,c)) # add node in visited

            while q:
                x, y = q.popleft() # pops the first added node in queue since it's BFS
                directions = [[0,1], [1,0], [0,-1], [-1,0]] # define bottom, right, top, left

                for dx, dy in directions:
                    rx, ry = x + dx, y + dy # add direction to our node
                    
                    # check if node + direction is in grid and is an island and not visited 
                    if rx in range(rows) and ry in range(cols) and grid[rx][ry] == "1" and (rx, ry) not in visited:
                        q.append((rx, ry)) # add to queue
                        visited.add((rx, ry)) # add to visited