<reponame>adaggarwal/leetcode1992<filename>src/651-700/695.py
'''

695. Max Area of Island

Given a non-empty 2D array grid of 0's and 1's, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:
[[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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

'''
class Solution:
    def maxAreaOfIsland(self, grid):
        
        #a set to store the elements visited in the past; use a set so that search is O(1)
        visitedNode = set()
        maxArea = 0

        #a stack is needed to store the tuple coordinate values to apply localized DFS on a seed
        stack = []
        
        #traverse through the grid in O(n); n -> elements in the grid (row*column)
        for rowIndex, rowValue in enumerate(grid):
            for columnIndex, columnValue in enumerate(rowValue):

                #skip the elements already visited O(1)
                if (rowIndex, columnIndex) in visitedNode:
                    continue

                localArea = 0

                #only consider the element if the value is non zero
                if columnValue:
                    stack = [(rowIndex, columnIndex)]

                #add it to the visited nodes O(1)
                visitedNode.add((rowIndex, columnIndex))

                #O(~k); k -> ~1 --> elements in the stack; but considering these k elements are
                # visited only once hence; k tends to 1 inside the nested for
                while stack:
                    locRow, locCol = stack.pop()

                    #what if each grid value had a weight to it? so don't solve for value 1s only
                    localArea += grid[locRow][locCol]

                    #try to visit the DFS neighbors of this Seed
                    for neighbor in [(locRow-1, locCol), (locRow+1, locCol), 
                    (locRow, locCol-1), (locRow, locCol+1)]:
                        #before counting the neighbor, validate it
                        if (0 <= neighbor[0] < len(grid)) and (0<= neighbor[1] < len(grid[0])) \
                        and (neighbor not in visitedNode) and (grid[neighbor[0]][neighbor[1]]):

                            #add to the stack and count the node visited so that it is not visited again
                            stack.append(neighbor)
                            visitedNode.add(neighbor)

                #each time the stack is emptied, the area of the island was calculated, update the global maxima
                maxArea = max(maxArea, localArea)
        
        
        return maxArea


x = Solution()
ar = x.maxAreaOfIsland([[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]])

print('Area = {}'.format(ar))
'''

695. Max Area of Island

Given a non-empty 2D array grid of 0's and 1's, 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.

Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)

Example 1:
[[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]]
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
[[0,0,0,0,0,0,0,0]]
Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.

'''
class Solution:
    def maxAreaOfIsland(self, grid):
        
        #a set to store the elements visited in the past; use a set so that search is O(1)
        visitedNode = set()
        maxArea = 0

        #a stack is needed to store the tuple coordinate values to apply localized DFS on a seed
        stack = []
        
        #traverse through the grid in O(n); n -> elements in the grid (row*column)
        for rowIndex, rowValue in enumerate(grid):
            for columnIndex, columnValue in enumerate(rowValue):

                #skip the elements already visited O(1)
                if (rowIndex, columnIndex) in visitedNode:
                    continue

                localArea = 0

                #only consider the element if the value is non zero
                if columnValue:
                    stack = [(rowIndex, columnIndex)]

                #add it to the visited nodes O(1)
                visitedNode.add((rowIndex, columnIndex))

                #O(~k); k -> ~1 --> elements in the stack; but considering these k elements are
                # visited only once hence; k tends to 1 inside the nested for
                while stack:
                    locRow, locCol = stack.pop()

                    #what if each grid value had a weight to it? so don't solve for value 1s only
                    localArea += grid[locRow][locCol]

                    #try to visit the DFS neighbors of this Seed
                    for neighbor in [(locRow-1, locCol), (locRow+1, locCol), 
                    (locRow, locCol-1), (locRow, locCol+1)]:
                        #before counting the neighbor, validate it
                        if (0 <= neighbor[0] < len(grid)) and (0<= neighbor[1] < len(grid[0])) \
                        and (neighbor not in visitedNode) and (grid[neighbor[0]][neighbor[1]]):

                            #add to the stack and count the node visited so that it is not visited again
                            stack.append(neighbor)
                            visitedNode.add(neighbor)

                #each time the stack is emptied, the area of the island was calculated, update the global maxima
                maxArea = max(maxArea, localArea)
        
        
        return maxArea


x = Solution()
ar = x.maxAreaOfIsland([[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]])

print('Area = {}'.format(ar))
695. Max Area of Island  Given a non-empty 2D array grid of 0's and 1's, 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.  Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)  Example 1: [[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]] Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally. Example 2: [[0,0,0,0,0,0,0,0]] Given the above grid, return 0. Note: The length of each dimension in the given grid does not exceed 50. #a set to store the elements visited in the past; use a set so that search is O(1) #a stack is needed to store the tuple coordinate values to apply localized DFS on a seed #traverse through the grid in O(n); n -> elements in the grid (row*column) #skip the elements already visited O(1) #only consider the element if the value is non zero #add it to the visited nodes O(1) #O(~k); k -> ~1 --> elements in the stack; but considering these k elements are # visited only once hence; k tends to 1 inside the nested for #what if each grid value had a weight to it? so don't solve for value 1s only #try to visit the DFS neighbors of this Seed #before counting the neighbor, validate it #add to the stack and count the node visited so that it is not visited again #each time the stack is emptied, the area of the island was calculated, update the global maxima