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)
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.