Skip to content

Volume ITechnology

4.20.3 — Max Area of Island ​

LeetCode 695 · Medium

The problem ​

Return the number of cells in the largest island. Return 0 if there is no land.

0 0 1 0 0
0 0 0 0 0
0 1 1 0 1        →  4    (the three-cell island plus... no —
0 1 0 0 1             the largest here is the pair on the right joined
                      with the one below it: count them per island)

In plain English, given a 2D binary grid, an island is a group of 1s connected 4-directionally (horizontal or vertical). The area of an island is the number of cells it contains. You need to return the maximum area of any island in the grid. If the grid contains only 0s, return 0. Grid dimensions typically range up to 50x50.

The pattern ​

4.20.1 Number of Islands with one change: the flood fill returns how many cells it visited, instead of returning nothing.

Each cell contributes 1, plus whatever the four recursive calls contribute. Water and already-visited cells contribute 0.

That is the whole difference, and notice how small it is. The flood fill is a template, and problems differ only in what they collect while flooding.

A picture to hold in mind ​

Think of the bucket-of-paint analogy from Number of Islands. You are still dumping red paint on unvisited land. But this time, you have an assistant with a tally counter. Every time the paint spreads to a new square of land, the assistant clicks the counter. When the paint stops spreading, the assistant tells you the final tally for that island. You write it down. Then you move on, looking for the next unpainted island. At the end of the day, you look at your notepad and circle the biggest number you wrote down.

The brute force, and where it wastes work ​

A brute force method might be to start a BFS/DFS from every single 1 in the grid and count the reachable 1s without mutating the grid (re-creating a visited set every time). If the entire grid is one massive island of size N, starting a full search from every single cell would take O(N) work per cell, leading to O(N^2) time complexity. By mutating the grid as we go, we ensure each cell is part of only one search, keeping it firmly at O(N).

The solution ​

python
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        rows, cols = len(grid), len(grid[0])  # (1)

        def area(r: int, c: int) -> int:  # (2)
            if r < 0 or r >= rows or c < 0 or c >= cols:  # (3)
                return 0
            if grid[r][c] != 1:  # (4)
                return 0                     # water, or already counted

            grid[r][c] = 0                   # (5) mark before recursing

            return (1  # (6)
                    + area(r + 1, c)
                    + area(r - 1, c)
                    + area(r, c + 1)
                    + area(r, c - 1))

        best = 0  # (7)
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == 1:  # (8)
                    best = max(best, area(r, c))

        return best
ts
function maxAreaOfIsland(grid: number[][]): number {
  const rows = grid.length, cols = grid[0].length;  // (1)

  function area(r: number, c: number): number {  // (2)
    if (r < 0 || r >= rows || c < 0 || c >= cols) return 0;  // (3)
    if (grid[r][c] !== 1) return 0;  // (4)

    grid[r][c] = 0;  // (5)

    return 1 + area(r + 1, c) + area(r - 1, c)  // (6)
             + area(r, c + 1) + area(r, c - 1);
  }

  let best = 0;  // (7)
  for (let r = 0; r < rows; r++)
    for (let c = 0; c < cols; c++)
      if (grid[r][c] === 1) best = Math.max(best, area(r, c));  // (8)

  return best;
}

The 1 + counts this cell; the four calls count the rest of the island.

Marking before recursing is what makes each cell counted exactly once. Marking afterwards would let a cell be reached again through a neighbour and counted twice, and would also loop forever.

best starts at 0, so a grid with no land returns 0 with no special case.

Everything else is identical to 4.20.1.

Line by line ​

(1) The grid's size.

(2) area(r, c) returns the size of the island containing (r, c), and sinks it as it goes. It is 4.20.1 Number of Islands with a number passed back up instead of nothing.

(3) Off the grid adds no area.

(4) Water, or land already counted, adds no area.

(5) Sink this cell before visiting neighbours, so it is never counted twice and the walk cannot loop.

(6) This cell counts as 1, plus the area reachable through each of its four neighbours. Each neighbour's call returns the size of the part of the island it reaches, and every land cell is counted exactly once, because it is sunk the first time it is reached.

(7) The biggest island seen so far.

(8) Each unsunk land cell starts a new island. Measure it and keep the biggest.

Trace ​

Consider a tiny 1D grid [1, 1, 0].

StepActionStateReturn Value
1Loop r=0, c=0. Call area(0, 0)Grid: [1, 1, 0]. best = 0
2Inside area(0, 0). Mark grid[0][0] = 0Grid: [0, 1, 0]
3Calls area(0, 1)
4Inside area(0, 1). Mark grid[0][1] = 0Grid: [0, 0, 0]
5area(0, 1) calls neighborsAll return 0Returns 1 + 0 = 1
6Back to area(0, 0)Returns 1 + 1 = 2
7Update bestbest = max(0, 2) = 2
8Loop continues... calls area(0, 1)Returns 0 (it's water now)
9FinishReturns 2

Edge cases ​

  • No land. The answer is 0.
  • One big island covering everything. The answer is rows × cols.
  • Islands touching only at corners are separate.

Complexity ​

O(rows \times cols) time and space. To break it down: Time complexity is O(rows \times cols) because the nested for loops iterate over every cell exactly once, doing O(1) work to check if grid[r][c] == 1. When we do find a 1, the area DFS visits it, mutates it to 0, and never visits it again. Thus, across the entire execution, each cell is processed only a constant number of times. Space complexity is O(rows \times cols) because the recursion call stack could potentially go as deep as the total number of cells if the entire grid is one long snake-like island.

The family, made explicit ​

The flood fill accumulates something. Which something is the whole problem:

problemthe flood returns
Number of Islandsnothing — you count the calls
Max Area of Islandthe cell count
Count Sub Islandswhether every cell was also land in a second grid
Number of Closed Islandswhether the island ever touched the border
Number of Distinct Islandsthe list of cell offsets, used as a shape fingerprint
Island Perimeterthe number of edges facing water or the outside

Number of Distinct Islands combines two chapters. Two islands are the same if one can slide onto the other, so the fingerprint is the set of cell positions relative to the island's first cell. Record those offsets during the flood, turn them into a tuple, and count the distinct tuples with a set. That is 4.4.4 Group Anagrams's fingerprint idea applied to shapes.

What the interviewer will push on ​

"How is this different from counting islands?" The flood returns a count instead of nothing.

"Why mark before recursing?" Otherwise cells are counted twice and the recursion never ends.

"What if you could not modify the grid?" A separate visited array, same complexity.

"How would you find the largest island you could make by flipping one water cell to land?" That is LeetCode 827, and it is the interesting follow-up. Flood once, giving each island an id and storing its size in a map. Then, for every water cell, look at its four neighbours, collect their distinct island ids, and add those sizes plus one. The word "distinct" is where people go wrong: two neighbours may belong to the same island and must not be counted twice. It is still O(rows \times cols).

One thing to volunteer: name the family. "This is the flood fill again; the only question in these problems is what you accumulate while flooding." Saying it turns six problems into one.

Next: 4.20.4 Pacific Atlantic Water Flow — where the trick is to run the search backwards.

Combine chapters into one PDF

Pick the chapters you want. They print in the order you pick them.

Volume I — Technology
Part 0 — Retention & Notation
Part 1 — Foundations of Computation
Part 2 — Operating Systems
2.1 The Kernel
2.2 Processes
2.3 Threads & Scheduling
2.4 Concurrency Under the Hood
2.5 Memory Management
2.6 File Systems
2.7 Input/Output
2.8 Linux for Engineers
2.9 Windows & macOS in Practice
Part 3 — Languages, Compilers & Runtimes
3.6 JavaScript & V8
3.7 TypeScript
3.8 Node.js Internals
3.13 Python & CPython
3.14 FastAPI & Production Python
Part 4 — Data Structures & Algorithms
4.0 Classic Problems — Before NeetCode
4.4 Arrays & Hashing — Problems
4.5 Two Pointers
4.6 Sliding Window
4.8 Stack — Problems
4.9 Linked List — Problems
4.11 Binary Search — Problems
4.13 Trees
4.14 Tree — Problems
4.15 Trie — Problems
4.17 Heap — Problems
4.18 Backtracking — Problems
4.19 Graphs
4.20 Graph — Problems
4.21 Advanced Graph — Problems
4.23 1-D DP — Problems
4.24 2-D DP — Problems
4.26 Greedy — Problems
4.27 Interval — Problems
4.28 Math & Geometry — Problems
4.30 Bit Manipulation — Problems
Part 5 — Networking & the Web
5.3 IP
5.4 Transport
5.6 HTTP
Part 6 — Frontend Engineering
6.1 Browser Internals
6.2 HTML & CSS Mastery
6.3 JavaScript in the Browser
6.4 React, from First Component to Full Shop
6.5 Frameworks & Rendering
6.8 UI Engineering & Patterns
Part 7 — Databases & Storage
7.2 SQL Mastery
7.3 Storage Engine Internals
7.4 Transactions
7.5 NoSQL Taxonomy
7.8 Analytics & Big Data
Part 8 — Security, Identity & Cryptography
8.2 Cryptography
8.3 Protocols of Trust
8.4 Identity: AuthN & AuthZ
8.5 Application Security
8.6 Infrastructure Security
Part 9 — Software Design (LLD)
9.2 OOP Foundations
9.3 Design Principles
9.4 Design Patterns
9.5 Concurrency
9.6 API Design
9.7 LLD Interview Machines
9.9 Node/Express Production Playbook
Part 10 — Distributed Systems & HLD
10.7 Consistency & Consensus
10.8 Messaging & Microservices
10.14 Caching
Building blocks from the design seat
Part 11 — System Design Case Studies
Part 12 — AI & ML Engineering
12.1 What AI Engineering Is
12.2 The Math You Need
12.3 Classical Machine Learning
12.4 Data for ML
12.5 Deep Learning
12.6 Embeddings & Vector Search
12.7 Transformers & LLMs
12.8 Building with LLMs
12.9 Retrieval-Augmented Generation
12.10 Agents
12.11 Adapting Models
12.12 Production AI
12.13 Multimodal AI
12.14 AI Security & Governance
12.15 Case Studies & Capstone
Part 13 — Cloud, DevOps & Infrastructure
13.11 Git, from First Commit to Team Workflow
Part 14 — Containers: Docker & Kubernetes
14.1 Foundations
14.2 Docker
14.3 Kubernetes
14.4 Kubernetes on Azure
Part 15 — The Craft & Career
Nothing picked yet