from collections import deque
class Solution:
  def maxAreaOfIsland(self, matrix):
    biggestIslandArea = 0
    # TODO: Write your code here
    # loop through matrix to see if we can find an island
    # call visitNeighborIsland to calculate the size of island
    for row in range(len(matrix)):
      for col in range(len(matrix[0])):
        if matrix[row][col] == 1:
          currSizeIsland = self.visitNeighborIslandBFS(row, col, matrix)
          biggestIslandArea = max(biggestIslandArea, currSizeIsland)
    return biggestIslandArea
  
  def visitNeighborIslandDFS(self, row, col, matrix, currSize):
    if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
      return 0
    if matrix[row][col] == 0:
      return 0
    currSize = 1
    matrix[row][col] = 0
    currSize += self.visitNeighborIslandDFS(row + 1, col, matrix, currSize) + \
    self.visitNeighborIslandDFS(row - 1, col, matrix, currSize) + \
    self.visitNeighborIslandDFS(row, col + 1 , matrix, currSize) + \
    self.visitNeighborIslandDFS(row, col - 1, matrix, currSize)
    return currSize
  def visitNeighborIslandBFS(self, row, col, matrix):
    neighbors = deque([(row, col)])
    currIslandsize = 0
    while neighbors:
      row, col = neighbors.popleft()

      if row < 0 or row >= len(matrix) or col < 0 or col >= len(matrix[0]):
        continue
      if matrix[row][col] == 0:
        continue

      # mark it 0 and add 1 to size
      matrix[row][col] = 0 
      currIslandsize += 1
      # add all adjcent node for processing
      neighbors.extend([(row + 1, col)])
      neighbors.extend([(row - 1, col)])
      neighbors.extend([(row, col + 1)])
      neighbors.extend([(row, col - 1)])
    return currIslandsize