Quick Overview

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.

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/

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

  1. Use DFS or BFS to explore each unvisited land cell and compute its island area.
  2. Track visited cells to avoid recounting and infinite loops.
  3. Check bounds carefully when exploring the four neighbors of a cell.

Loading coding console...

Show the approach

Approach

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)