Leetcode 695. Max Area of Island

Problem

You are given a 2D grid where each cell contains either 0 (water) or 1 (land). An island is defined as a group of land cells that are connected horizontally or vertically (4-directional connectivity). Diagonal connections do not count.

Your task is to find the area of the largest island in the grid. The area of an island is the number of land cells it contains. If there are no islands in the grid, return 0.

Requirements

1. Implement a function that takes a 2D grid of integers (0s and 1s) as input
2. Return the maximum area among all islands in the grid
3. Only consider 4-directional connectivity (up, down, left, right)
4. Return 0 if no land cells exist in the grid
5. The function should handle grids of any valid dimensions

Constraints

• m == grid.length (number of rows)
• n == grid[i].length (number of columns)
• 1 <= m, n <= 50
• grid[i][j] is either 0 or 1
• Time complexity: O(m × n) is expected
• Space complexity: O(m × n) for the recursion stack or visited tracking

Examples

Example 1:

Input: grid = [ [1,1,0,0,0], [1,1,0,0,0], [0,0,0,1,1], [0,0,0,1,1] ] Output: 4 Explanation: There are two islands with areas 4 and 4. The maximum is 4.

Example 2:

Input: grid = [ [0,0,0], [0,0,0] ] Output: 0 Explanation: No land cells exist, so the answer is 0.

Example 3:

Input: grid = [ [1,1,1,0,0], [0,0,1,0,1], [0,0,1,1,1] ] Output: 6 Explanation: The center/right island has cells at positions forming a connected component of size 6.

Hint 1: Traversal Strategy Consider using a depth-first search (DFS) or breadth-first search (BFS) to explore each island. When you encounter a land cell that hasn't been visited, start a traversal from that cell to count all connected land cells.

Hint 2: Avoiding Revisits To prevent counting the same cell multiple times, you can either mark visited cells in place (by changing 1s to 0s) or use a separate visited set to track which cells you've already explored.

Hint 3: Four Directions For each land cell, check all four adjacent cells (up, down, left, right). Make sure to validate that the adjacent position is within grid bounds and is also a land cell before continuing the traversal.

Full Solution ` def maxIslandArea(grid): if not grid or not grid[0]: return 0

rows = len(grid)
cols = len(grid[0])
max_area = 0

def dfs(r, c):
    # Base cases: out of bounds or water cell
    if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == 0:
        return 0
    
    # Mark current cell as visited by setting it to 0
    grid[r][c] = 0
    
    # Count current cell plus all connected land cells in 4 directions
    area = 1
    area += dfs(r + 1, c)  # down
    area += dfs(r - 1, c)  # up
    area += dfs(r, c + 1)  # right
    area += dfs(r, c - 1)  # left
    
    return area

# Iterate through each cell in the grid
for r in range(rows):
    for c in range(cols):
        if grid[r][c] == 1:
            # Found an unvisited island, explore it
            current_area = dfs(r, c)
            max_area = max(max_area, current_area)

return max_area

`

Approach:

1. Iterate through the grid: Check each cell to find unvisited land cells (value = 1)
2. DFS exploration: When we find a land cell, perform a depth-first search to explore the entire island
3. Mark as visited: As we explore, mark cells as visited by setting them to 0 (alternatively, use a separate visited set)
4. Count area: The DFS recursively counts all connected land cells in the 4 directions
5. Track maximum: Keep track of the largest area found across all islands

Time Complexity: O(m × n) where m is the number of rows and n is the number of columns. We visit each cell at most once.

Space Complexity: O(m × n) in the worst case for the recursion stack (when the entire grid is one island). If we used an iterative BFS with a queue, the space would still be O(m × n) in the worst case.

Alternative approach (BFS):

You could also use breadth-first search with a queue instead of recursive DFS. The time and space complexity would remain the same, but BFS might be preferred in environments with limited stack space.