LC 695 - Max Area of Island

Question

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.

Links

Question here and solution here

Solution

concept

This question is very similar to 200. Number of Islands

code

class Solution:
	"""
	DFS
	"""
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visited = set()
        directions = [[0,1], [1,0], [0,-1], [-1,0]]
        ans = float("-inf")

        def dfs(r, c):
            if (r < 0 or r >= ROW or
                c < 0 or c >= COL or
                grid[r][c] == 0 or
                (r, c) in visited):
                return 0

            visited.add((r,c))
            area = 1
            for dr, dc in directions:
                area += dfs(r + dr, c + dc)
            return area
        
        for r in range(ROW):
            for c in range(COL):
                area = dfs(r,c)
                ans = max(ans, area)

        return ans
        
class Solution:
	"""
	BFS
	"""
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROW, COL = len(grid), len(grid[0])
        visited = set()
        directions = [[0,1], [1,0], [0,-1], [-1,0]]
        ans = float("-inf")

        def bfs(r, c):
            q = deque()
            visited.add((r,c))
            q.append((r,c))
            area = 1

            while q:
                row, col = q.popleft()
                for dr, dc in directions:
                    n_row, n_col = row + dr, col + dc
                    if (0 <= n_row < ROW and
                        0 <= n_col < COL and
                        grid[n_row][n_col] == 1 and
                        (n_row, n_col) not in visited):
                        
                        q.append((n_row, n_col))
                        visited.add((n_row, n_col))
                        area += 1

            return area
        
        for r in range(ROW):
            for c in range(COL):
                if grid[r][c] == 1 and (r,c) not in visited:
                    area = bfs(r,c)
                    ans = max(ans, area)

        return 0 if ans == float("-inf") else ans
        
class NeetSolution:
	"""
	DFS
	"""
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        ROWS, COLS = len(grid), len(grid[0])
        visit = set()

        def dfs(r, c):
            if (
                r < 0
                or r == ROWS
                or c < 0
                or c == COLS
                or grid[r][c] == 0
                or (r, c) in visit
            ):
                return 0
            visit.add((r, c))
            return 1 + dfs(r + 1, c) + dfs(r - 1, c) + dfs(r, c + 1) + dfs(r, c - 1)

        area = 0
        for r in range(ROWS):
            for c in range(COLS):
                area = max(area, dfs(r, c))
        return area

Complexity

time: $O(mn)$
space: $O(mn)$