LT #695: Max Area of Island

Day: 1
Type: Graphs
Level: Easy
Link: https://leetcode.com/problems/max-area-of-island/description/

TL:DR

Algorithm: BFS/DFS
Approach: Run BFS on each element of the grid. Count the number of “1”s (islands) for each BFS. Keep a variable to track of the count and find max when we finish all the nodes.

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 count the number of “1”s in each cluster.

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 — and the area for each cluster. From the image, Island Cluster #1 has max area.

3. Start with creating variables.

visited = set() # keep track of nodes that are already visited to skip running bfs
maxArea = 0 # stores the max area after each bfs run

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)
                    maxArea = max(tempArea, maxArea)
return maxArea 

6. Defining the BFS algorithm —

def bfs(r,c):
            q = collections.deque() # create queue to add nodes of islands
            q.append((r,c))
            visited.add((r,c)) # add node in visited
            tempArea = 1 # initialize tempArea with 1 as we are already traversing the node ((r,c))

            while q:
                x, y = q.popleft()
                directions = [[0,1], [1,0], [0,-1], [-1,0]]

                for dx, dy in directions:
                    rx, ry = x + dx, y + dy
                    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))
                        visited.add((rx,ry))
                        tempArea += 1 # increment when a new node is added to queue
            
            return tempArea