Find largest island area
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
##### Question
Given a 2D grid of 0s and 1s, find the largest area of a connected group of 1s (island) using 4-directional adjacency; return that area. (Variant of LeetCode 695 Max Area of Island.)
https://leetcode.com/problems/max-area-of-island/description/
Quick Answer: This question evaluates a candidate's ability to perform grid-based graph traversal and manage visited state, testing algorithmic skills in connected components and traversal techniques within algorithms and data structures.
Given a rectangular 2D grid of 0s and 1s, return the area of the largest island. An island is a maximal group of 1s connected 4-directionally (up, down, left, right). The area is the number of cells with value 1 in the island. If no land exists, return 0.
Constraints
- 1 <= m, n <= 200
- grid is an m x n matrix of integers
- grid[i][j] is 0 or 1
- Adjacency is 4-directional only
- Expected time complexity: O(m*n)
Solution
from typing import List
def max_island_area(grid: List[List[int]]) -> int:
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
visited = [[False] * n for _ in range(m)]
max_area = 0
for r in range(m):
for c in range(n):
if grid[r][c] == 1 and not visited[r][c]:
area = 0
stack = [(r, c)]
visited[r][c] = True
while stack:
x, y = stack.pop()
area += 1
# Explore 4-directional neighbors
if x > 0 and grid[x - 1][y] == 1 and not visited[x - 1][y]:
visited[x - 1][y] = True
stack.append((x - 1, y))
if x + 1 < m and grid[x + 1][y] == 1 and not visited[x + 1][y]:
visited[x + 1][y] = True
stack.append((x + 1, y))
if y > 0 and grid[x][y - 1] == 1 and not visited[x][y - 1]:
visited[x][y - 1] = True
stack.append((x, y - 1))
if y + 1 < n and grid[x][y + 1] == 1 and not visited[x][y + 1]:
visited[x][y + 1] = True
stack.append((x, y + 1))
if area > max_area:
max_area = area
return max_area
Explanation
Iterate through the grid. When an unvisited land cell (1) is found, perform an iterative DFS using a stack to traverse all connected land cells, marking them visited and counting the area. Track and return the maximum area over all discovered islands.
Time complexity: O(m*n). Space complexity: O(m*n).
Hints
- Use DFS or BFS to explore each unvisited land cell and compute its island area.
- Track visited cells to avoid recounting and infinite loops.
- Check bounds carefully when exploring the four neighbors of a cell.