695. Max Area of Island

Max Area of Island (LeetCode 695) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Graph DFS - Connected Components / Island Counting subpattern.

• NeetCode 150 · #81 of 150 · Graphs
• NeetCode 250 · #147 of 250 · Graphs

How to solve Max Area of Island

Max Area of Island is a DFS Connected Components problem, part of Graph Traversal Patterns (DFS & BFS). Use DFS to find connected components and count islands in grids. Flood fill and province counting problems.

Work towards the solution in these steps:

1. Consider the problem as finding connected components in a grid, where each component represents an island.
2. Use graph traversal techniques like Depth-First Search (DFS) or Breadth-First Search (BFS) to explore each island starting from unvisited land cells.
3. While traversing an island, keep track of the number of cells visited to calculate its area.

The reference solution runs in O(m * n) time and O(m * n) space.

The Max Area of Island solution and editorial walks through the full approach with reference code.

Problem statement

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.

Topics and companies

Topics: Array, Depth-First Search, Breadth-First Search, Union Find, Matrix.

Reported in interviews at Amazon, Bloomberg, DoorDash, eBay, Facebook, Google, LinkedIn, Microsoft, Oracle, Uber.

How to practise Max Area of Island on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(m * n) time and O(m * n) space.

Open Max Area of Island in the code editor, or read the Max Area of Island editorial for a worked solution with its approach and complexity analysis.

Where Max Area of Island sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Graph DFS - Connected Components / Island Counting subpattern
• The full DSA patterns sheet

Problems related to Max Area of Island

Other problems that use the same Graph DFS - Connected Components / Island Counting and Graph Traversal Patterns (DFS & BFS) techniques:

• Count Sub Islands — Medium, same subpattern
• Detonate the Maximum Bombs — Medium, same subpattern
• Evaluate Division — Medium, same subpattern
• Flood Fill — Easy, same subpattern
• Island Perimeter — Easy, same subpattern
• Keys and Rooms — Medium, same subpattern

Max Area of Island FAQ