Find the Max Area of an Island in Python

The challenge

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 1:

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.

Example 2:

Input: grid = [[0,0,0,0,0,0,0,0]]
Output: 0

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 50
  • grid[i][j] is either 0 or 1.

The solution in Python code

class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def get_neighbor(pos,grid): y,x = pos ns = [] if x>=1: ns.append((y,x-1)) if x<len(grid[0])-1: ns.append((y,x+1)) if y>=1: ns.append((y-1,x)) if y<len(grid)-1: ns.append((y+1,x)) return ns marked = set() land = [] for row in range(len(grid)): for col in range(len(grid[row])): if grid[row][col] == 1 and (row,col) not in marked: curr_land_len = 1 marked.add((row,col)) stack = [(row,col)] while stack: current = stack.pop() neighbor = get_neighbor(current,grid) for n in neighbor: y,x = n if grid[y][x] == 1 and (y,x) not in marked: marked.add((y,x)) curr_land_len += 1 stack.append((y,x)) land.append(curr_land_len) return (max(land) if len(land)!=0 else 0)
Code language: Python (python)
Tags:
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments