Max Area of Island - Practice Coding Problems

Max Area of Island - Problem

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.

Input & Output

Example 1 — Basic Grid

$ Input: grid = [[1,1,0,0],[1,1,0,0],[0,0,1,0]]

› Output: 4

💡 Note: The largest island is the top-left 2x2 square of 1's, which has area 4. The bottom-right single 1 has area 1.

Example 2 — All Water

$ Input: grid = [[0,0,0,0,0,0,0,0]]

› Output: 0

💡 Note: There are no islands (no 1's), so the maximum area is 0.

Example 3 — Single Large Island

$ Input: grid = [[1,1,1],[1,0,1],[1,1,1]]

› Output: 7

💡 Note: All 1's are connected except the center 0, forming one island with area 7.

Constraints

m == grid.length
n == grid[i].length
1 ≤ m, n ≤ 50
grid[i][j] is either 0 or 1

Visualization

Tap to expand

Understanding the Visualization

Input Grid

2D binary matrix with 1's (land) and 0's (water)

Find Islands

Use DFS/BFS to identify connected components of 1's

Track Max Area

Return the size of the largest island found

Key Takeaway

🎯 Key Insight: Use DFS/BFS to explore connected components and mark visited cells to avoid double counting

Asked in

F Facebook 65 a Amazon 45 G Google 35 M Microsoft 28

The key insight is to use DFS or BFS to explore each island completely and mark visited cells to avoid recounting. The optimal approach is DFS with in-place marking, achieving Time: O(m×n), Space: O(m×n) for recursion stack.

Common Approaches

Approach	Time	Space	Notes
✓ Breadth-First Search	O(m×n)	O(min(m,n))	Use BFS with queue to explore islands level by level
Depth-First Search	O(m×n)	O(m×n)	Use DFS to traverse each island once and mark visited cells
Brute Force	O(m²×n²)	O(m×n)	Check every cell and count connected land cells without marking visited

Breadth-First Search — Algorithm Steps

Iterate through each cell in the grid
When we find unvisited land, start BFS using a queue
Mark current cell as visited and add neighbors to queue
Process all cells in queue level by level
Return total area of the island

Visualization

Tap to expand

Step-by-Step Walkthrough

Start

Add starting land cell to queue

Expand

Process queue and add neighbors level by level

Count

Count all cells processed from queue

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int i, j;
} Point;

int bfs(int** grid, int rows, int cols, int startI, int startJ) {
    Point* queue = (Point*)malloc(rows * cols * sizeof(Point));
    int front = 0, rear = 0;
    
    queue[rear++] = (Point){startI, startJ};
    grid[startI][startJ] = 0; // Mark as visited
    int area = 0;
    
    int directions[4][2] = {{0,1}, {0,-1}, {1,0}, {-1,0}};
    
    while (front < rear) {
        Point curr = queue[front++];
        area += 1;
        
        for (int d = 0; d < 4; d++) {
            int ni = curr.i + directions[d][0];
            int nj = curr.j + directions[d][1];
            if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] == 1) {
                grid[ni][nj] = 0; // Mark as visited
                queue[rear++] = (Point){ni, nj};
            }
        }
    }
    
    free(queue);
    return area;
}

int solution(int** grid, int rows, int cols) {
    if (rows == 0 || cols == 0) return 0;
    
    int maxArea = 0;
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < cols; j++) {
            if (grid[i][j] == 1) {
                int area = bfs(grid, rows, cols, i, j);
                if (area > maxArea) maxArea = area;
            }
        }
    }
    
    return maxArea;
}

int main() {
    // Simple parsing for demo - in practice would need robust JSON parsing
    int grid[3][4] = {{1,1,0,0},{1,1,0,0},{0,0,1,0}};
    int* gridPtrs[3] = {grid[0], grid[1], grid[2]};
    
    printf("%d\n", solution(gridPtrs, 3, 4));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(m×n)

Each cell is visited at most once during the entire algorithm

✓ Linear Growth

Space Complexity

O(min(m,n))

Queue size limited by the perimeter of the largest island

⚡ Linearithmic Space

125.0K Views

High Frequency

~15 min Avg. Time

5.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Breadth-First Search — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler