Max Area of Island
Max Area of Island is a medium graphs problem solved with the matrix graphs pattern.
The best approach, optimal (sink each island once), runs in O(m · n) time and O(m · n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (flood fill from every land cell) up.
Problem
You are given an m x n grid of 0s (water) and 1s (land). An island is a group of land cells joined horizontally or vertically; cells that only touch at a corner belong to different islands. Everything outside the grid is water.
The area of an island is the number of land cells in it. Return the largest area of any island in the grid, or 0 if the grid has no land.
Examples
Example 1
- Input
grid = [[1,1,0,0,1],[0,1,0,1,1],[0,0,0,0,1],[1,0,1,0,0]]- Output
4- Why
- The island on the right covers (0,4), (1,3), (1,4) and (2,4), which is 4 cells; the top-left island has only 3.
Example 2
- Input
grid = [[0,0,0],[0,0,0]]- Output
0- Why
- There is no land at all, so the largest area is 0.
Example 3
- Input
grid = [[1,0,1],[0,1,0],[1,0,1]]- Output
1- Why
- Cells that touch only at corners are separate islands, so every island has area 1.
Constraints
1 <= m, n <= 50where the grid has m rows and n columns.- Every cell is
0(water) or1(land). - Land cells are connected only up, down, left and right.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flood fill from every land cell) | O((m · n)²) | O(m · n) |
| Optimal (sink each island once) | O(m · n) | O(m · n) |
1Brute force (flood fill from every land cell)
O((m · n)²)Up to m · n starting cells, and each BFS can visit all m · n cells.O(m · n)The visited matrix and the queue for one BFS.Treat each land cell as a possible starting point. From each one, run a fresh BFS with a brand-new visited array and count how many cells it reaches. The largest count is the answer. Cells of the same island are explored again and again, which is what makes this slow.
- For every cell (i, j) that is land, create a fresh visited matrix.
- BFS from (i, j) over land neighbours, counting cells as they are dequeued.
- Keep the maximum count seen.
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
boolean[][] seen = new boolean[m][n];
ArrayDeque<int[]> q = new ArrayDeque<>();
q.add(new int[] { i, j });
seen[i][j] = true;
int area = 0;
while (!q.isEmpty()) {
int[] c = q.poll();
area++;
for (int[] d : dirs) {
int r = c[0] + d[0], s = c[1] + d[1];
if (r >= 0 && r < m && s >= 0 && s < n && grid[r][s] == 1 && !seen[r][s]) {
seen[r][s] = true;
q.add(new int[] { r, s });
}
}
}
best = Math.max(best, area);
}
}
return best;
}
}class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
best = 0
for i in range(m):
for j in range(n):
if grid[i][j] != 1:
continue
seen = [[False] * n for _ in range(m)]
q = deque([(i, j)])
seen[i][j] = True
area = 0
while q:
r, s = q.popleft()
area += 1
for dr, ds in ((1, 0), (-1, 0), (0, 1), (0, -1)):
a, b = r + dr, s + ds
if 0 <= a < m and 0 <= b < n and grid[a][b] == 1 and not seen[a][b]:
seen[a][b] = True
q.append((a, b))
best = max(best, area)
return bestclass Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
vector<vector<bool>> seen(m, vector<bool>(n, false));
queue<pair<int, int>> q;
q.push({i, j});
seen[i][j] = true;
int area = 0;
while (!q.empty()) {
auto [r, s] = q.front();
q.pop();
area++;
for (auto& d : dirs) {
int a = r + d[0], b = s + d[1];
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1 && !seen[a][b]) {
seen[a][b] = true;
q.push({a, b});
}
}
}
best = max(best, area);
}
}
return best;
}
};function maxAreaOfIsland(grid) {
const m = grid.length, n = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 1) continue;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
const q = [[i, j]];
seen[i][j] = true;
let area = 0;
for (let h = 0; h < q.length; h++) {
const [r, s] = q[h];
area++;
for (const [dr, ds] of dirs) {
const a = r + dr, b = s + ds;
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] === 1 && !seen[a][b]) {
seen[a][b] = true;
q.push([a, b]);
}
}
}
best = Math.max(best, area);
}
}
return best;
}2Optimal (sink each island once)
O(m · n)Each cell is pushed at most once and checks 4 neighbours.O(m · n)The stack can hold most of the grid when one island fills it.Scan the grid once. When you hit land, flood-fill its whole island with an explicit stack, turning every visited cell into water and counting it. Because sunk cells are water, no island is ever explored twice, so the total work is linear in the grid size.
- For each cell that is still land, set it to 0 and push it on a stack.
- Pop cells one by one, add 1 to the area, and push every land neighbour after setting it to 0.
- When the stack is empty, the island is fully counted; update the best area.
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m = grid.length, n = grid[0].length, best = 0;
int[][] dirs = { { 1, 0 }, { -1, 0 }, { 0, 1 }, { 0, -1 } };
ArrayDeque<int[]> st = new ArrayDeque<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
grid[i][j] = 0;
st.push(new int[] { i, j });
int area = 0;
while (!st.isEmpty()) {
int[] c = st.pop();
area++;
for (int[] d : dirs) {
int r = c[0] + d[0], s = c[1] + d[1];
if (r >= 0 && r < m && s >= 0 && s < n && grid[r][s] == 1) {
grid[r][s] = 0;
st.push(new int[] { r, s });
}
}
}
best = Math.max(best, area);
}
}
return best;
}
}class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
best = 0
for i in range(m):
for j in range(n):
if grid[i][j] != 1:
continue
grid[i][j] = 0
st = [(i, j)]
area = 0
while st:
r, s = st.pop()
area += 1
for dr, ds in ((1, 0), (-1, 0), (0, 1), (0, -1)):
a, b = r + dr, s + ds
if 0 <= a < m and 0 <= b < n and grid[a][b] == 1:
grid[a][b] = 0
st.append((a, b))
best = max(best, area)
return bestclass Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int m = grid.size(), n = grid[0].size(), best = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
vector<pair<int, int>> st;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (grid[i][j] != 1) continue;
grid[i][j] = 0;
st.push_back({i, j});
int area = 0;
while (!st.empty()) {
auto [r, s] = st.back();
st.pop_back();
area++;
for (auto& d : dirs) {
int a = r + d[0], b = s + d[1];
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] == 1) {
grid[a][b] = 0;
st.push_back({a, b});
}
}
}
best = max(best, area);
}
}
return best;
}
};function maxAreaOfIsland(grid) {
const m = grid.length, n = grid[0].length;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
let best = 0;
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (grid[i][j] !== 1) continue;
grid[i][j] = 0;
const st = [[i, j]];
let area = 0;
while (st.length) {
const [r, s] = st.pop();
area++;
for (const [dr, ds] of dirs) {
const a = r + dr, b = s + ds;
if (a >= 0 && a < m && b >= 0 && b < n && grid[a][b] === 1) {
grid[a][b] = 0;
st.push([a, b]);
}
}
}
best = Math.max(best, area);
}
}
return best;
}Edge cases to test
- No land anywhere (answer 0)
- The whole grid is land (answer m · n)
- Diagonal neighbours, which do not join islands
- A single row or a single column
Hints
Hint 1
An island is a connected component of land cells. How would you visit every cell of one component?
Hint 2
Count the cells while you flood-fill the component, and mark each one so it is never counted twice.
Hint 3
Mark visited land by turning it into water; then one scan over the grid touches each cell a constant number of times.
FAQ
What is the best time complexity for Max Area of Island?
Optimal (sink each island once) runs in O(m · n) time and O(m · n) extra space. Each cell is pushed at most once and checks 4 neighbours.
Which pattern does Max Area of Island use?
It is a graphs problem that uses the matrix graphs pattern. Other problems with the same pattern: Flood Fill, Maximum Number of Points From Grid Queries, Contain Virus.
Is there a brute force solution for Max Area of Island?
Yes. Brute force (flood fill from every land cell) takes O((m · n)²) time and O(m · n) space. Treat each land cell as a possible starting point.
Which edge cases should I test for Max Area of Island?
No land anywhere (answer 0); The whole grid is land (answer m · n); Diagonal neighbours, which do not join islands; A single row or a single column.