[Problem] Max Area of Island

Description

You are given an m x n binary matrix grid. An island is a group of 1's (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.

The area of an island is the number of cells with a value 1 in the island.

Return the maximum area of an island in grid. If there is no island, return 0.

Example

Input: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output: 6
Explanation: The answer is not 11, because the island must be connected 4-directionally.

Approach

Fundamental graph problem, solved through DFS. If we are on a land square and explore every square connected to it 4-directionally (and recursively squares connected to those squares, and so on), then the total number of squares explored will be the area of that connected shape.

To ensure we don't count squares in a shape more than once, let's use visited to keep track of squares we haven't visited before. It will also prevent us from counting the same shape more than once.

Time complexity:

Time Complexity: O(R∗C), where R is the number of rows in the given grid, and C is the number of columns. We visit every square once.

Solution

from collections import defaultdict

class Solution(object):
  def maxAreaOfIsland(self, grid):
      area = defaultdict(int)
      dx, dy = [1, 0, -1, 0], [0, 1, 0, -1]
      visited = set()

      def dfs(x, y, sector):
          visited.add((x, y))
          area[sector] += 1
          for i in range(4):
              nextx, nexty = x + dx[i], y + dy[i]
              if nextx < 0 or nextx >= len(grid[0]) or nexty < 0 or nexty >= len(grid):
                  continue
              #print(nextx, nexty)
              if (nextx, nexty) not in visited and grid[nexty][nextx]:
                  dfs(nextx, nexty, sector)

      area_cnt = 0
      for x in range(len(grid[0])):
          for y in range(len(grid)):
              #print(i, j, visited)
              if grid[y][x] and (x, y) not in visited:
                  dfs(x, y, area_cnt)
                  area_cnt += 1

      #print(area)
      max_area = 0
      for key in area:
          max_area = max(max_area, area[key])
      return max_area