keetcoder

# 695. Max Area of Island

LeetCode Problem Link (opens new window)

Given a binary matrix grid with dimensions m x n, each 1 represents a piece of land, and each 0 represents water. An island consists of a group of connected lands (horizontally or vertically adjacent). The area of an island is the number of 1's in the island. The task is to find the maximum area of all the islands in the grid. If there are no islands, return 0.

Diagram

  • 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 should be 6, as the island can only be formed by 1s that are adjacent horizontally or vertically.

# Approach

Note that each island can only be formed by adjacent lands in the horizontal or vertical directions.

This means that diagonal connections do not count. For example, in the second example, there are three islands.

This problem can be solved using basic DFS or BFS techniques to explore the number of "1"s in each island and then find the maximum.

The idea is straightforward; the real challenge is understanding the DFS and BFS theoretical foundations. If you need more understanding of these foundations, check the detailed explanations here:

# DFS

Many people write DFS based on intuition, sometimes including termination conditions to pass, and sometimes without them but still passing!

This involves two methods of writing DFS.

Version One: DFS processes neighboring nodes of the current node. The counter is set in the main function when a land is encountered, marking the count as 1, and DFS continues for adjacent lands.

// Version One
class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // Four directions
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // Out of bounds, skip
            if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // Not visited and is land

                visited[nextx][nexty] = true;
                count++;
                dfs(grid, visited, nextx, nexty);
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));

        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 1;  // Count as 1, with DFS handling the next lands
                    visited[i][j] = true;
                    dfs(grid, visited, i, j); // Mark connected lands as visited
                    result = max(result, count);
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

Version Two: DFS processes the current node. When an island is encountered, set the count as 0 in the main function, and start counting from 1 upon entering DFS.

// Version Two
class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // Four directions
    void dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        if (visited[x][y] || grid[x][y] == 0) return; // Termination condition
        visited[x][y] = true;
        count++;
        for (int i = 0; i < 4; i++) {
            int nextx = x + dir[i][0];
            int nexty = y + dir[i][1];
            if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue;  // Out of bounds, skip
            dfs(grid, visited, nextx, nexty);
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0; // Count as 0 first, and increment in DFS
                    dfs(grid, visited, i, j); // Mark connected lands as visited
                    result = max(result, count);
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

From the comments, we can see that in Version One, the counter is incremented in the main function, and further counting is done in DFS. In Version Two, counting is entirely handled within DFS.

For more details on these different approaches, please refer to DFS and BFS Detailed Explanation (opens new window).

# BFS

Regarding Breadth-First Search, if you're not familiar, check here: BFS Detailed Explanation (opens new window).

Here is the BFS solution:

class Solution {
private:
    int count;
    int dir[4][2] = {0, 1, 1, 0, -1, 0, 0, -1}; // Four directions
    void bfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int x, int y) {
        queue<int> que;
        que.push(x);
        que.push(y);
        visited[x][y] = true; // Marking visited
        count++;
        while(!que.empty()) {
            int xx = que.front();que.pop();
            int yy = que.front();que.pop();
            for (int i = 0 ;i < 4; i++) {
                int nextx = xx + dir[i][0];
                int nexty = yy + dir[i][1];
                if (nextx < 0 || nextx >= grid.size() || nexty < 0 || nexty >= grid[0].size()) continue; // Out of bounds
                if (!visited[nextx][nexty] && grid[nextx][nexty] == 1) { // Not visited and is land
                    visited[nextx][nexty] = true;
                    count++;
                    que.push(nextx);
                    que.push(nexty);
                }
            }
        }
    }

public:
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        vector<vector<bool>> visited = vector<vector<bool>>(n, vector<bool>(m, false));
        int result = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!visited[i][j] && grid[i][j] == 1) {
                    count = 0;
                    bfs(grid, visited, i, j); // Mark connected lands as visited
                    result = max(result, count);
                }
            }
        }
        return result;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

# Other Languages Versions

# Java

# DFS

// DFS
class Solution {
    int[][] dir = {
        {0, 1}, // right
        {1, 0}, // down
        {0, -1}, // left
        {-1, 0} // up
    };
    boolean visited[][];
    int count;
    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(visited[i][j] == false && grid[i][j] == 1){
                    count = 0;
                    dfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    private void dfs(int[][] grid, int x, int y){
        if(visited[x][y] == true || grid[x][y] == 0)
            return;
        
        visited[x][y] = true;
        count++;

        for(int i = 0; i < 4; i++){
            int nextX = x + dir[i][0];
            int nextY = y + dir[i][1];

            if(nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length)
                continue;
            dfs(grid, nextX, nextY);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

# BFS

// BFS
class Solution {
    int[][] dir = {
        {0, 1}, {1, 0}, {0, -1}, {-1, 0}
    };

    int count;
    boolean visited[][];

    public int maxAreaOfIsland(int[][] grid) {
        int res = 0;
        visited = new boolean[grid.length][grid[0].length];
        
        for(int i = 0; i < grid.length; i++){
            for(int j = 0; j < grid[0].length; j++){
                if(visited[i][j] == false && grid[i][j] == 1){
                    count = 0;
                    bfs(grid, i, j);
                    res = Math.max(res, count);
                }
            }
        }
        return res;
    }
    private void bfs(int[][] grid, int x, int y){
        Queue<Integer> que = new LinkedList<>();
        que.offer(x);
        que.offer(y);
        visited[x][y] = true;
        count++;
        
        while(!que.isEmpty()){
            int currX = que.poll();
            int currY = que.poll();

            for(int i = 0; i < 4; i++){
                int nextX = currX + dir[i][0];
                int nextY = currY + dir[i][1];
                
                if(nextX < 0 || nextY < 0 || nextX >= grid.length || nextY >= grid[0].length)
                    continue;
                if(visited[nextX][nextY] == false && grid[nextX][nextY] == 1){
                    que.offer(nextX);
                    que.offer(nextY);
                    visited[nextX][nextY] = true;
                    count++;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

# Optimized DFS (Sink the land when found)

// This uses Depth-First Search DFS to solve the problem. We use DFS to calculate the area of any one island, and maintain the maximum island area calculated as the result. To avoid recalculation of any island, we "sink" the island by marking its land as 0 during DFS.
public int maxAreaOfIsland(int[][] grid) {
    int res = 0;
    for(int i = 0;i < grid.length;i++){
        for(int j = 0;j < grid[0].length;j++){
            // Calculate and "sink" each found island
            if(grid[i][j] == 1){
                // Update max island area
                res = Math.max(res,dfs(grid,i,j));
            }
        }
    }
    return res;
}
public int dfs(int[][] grid,int i,int j){
    // Boundary condition: if out of bounds or on water
    if(i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == 0) return 0;
    // Sink the land
    grid[i][j] = 0;
    // Calculate current island's area
    return 1 + dfs(grid,i - 1,j) +
               dfs(grid,i + 1,j) +
               dfs(grid,i,j + 1) +
               dfs(grid,i,j - 1);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

# Python

# BFS

class Solution:
    def __init__(self):
        self.count = 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # Unlike problem 200, the grid here contains ints!

        # BFS
        if not grid: return 0

        m, n = len(grid), len(grid[0])
        visited = [[False for i in range(n)] for j in range(m)]

        result = 0
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == 1:
                    # For each new island
                    self.count = 0
                    self.bfs(grid, visited, i, j)
                    result = max(result, self.count)

        return result

    def bfs(self, grid, visited, i, j):
        self.count += 1
        visited[i][j] = True    

        queue = collections.deque([(i, j)])
        while queue:
            x, y = queue.popleft()
            for new_x, new_y in [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]) and not visited[new_x][new_y] and grid[new_x][new_y] == 1:
                    visited[new_x][new_y] = True
                    self.count += 1
                    queue.append((new_x, new_y))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# DFS

class Solution:
    def __init__(self):
        self.count = 0

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # DFS
        if not grid: return 0

        m, n = len(grid), len(grid[0])
        visited = [[False for _ in range(n)] for _ in range(m)]

        result = 0
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == 1:
                    self.count = 0
                    self.dfs(grid, visited, i, j)
                    result = max(result, self.count)
        return result
        
    def dfs(self, grid, visited, x, y):
        if visited[x][y] or grid[x][y] == 0:
            return 
        visited[x][y] = True
        self.count += 1
        for new_x, new_y in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
            if 0 <= new_x < len(grid) and 0 <= new_y < len(grid[0]): 
                self.dfs(grid, visited, new_x, new_y)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

# JavaScript

var maxAreaOfIsland = function (grid) {
    let dir = [[0, 1], [1, 0], [-1, 0], [0, -1]]; // Four directions
    
    let visited = new Array(grid.length).fill().map(() => Array(grid[0].length).fill(false))
    
    let dfs = (grid, visited, x, y, m) => {
        for (let i = 0; i < 4; i++) {
            let nextX = x + dir[i][0]
            let nextY = y + dir[i][1]
            if (nextX < 0 || nextX >= grid.length || nextY < 0 || nextY >= grid[0].length)
                continue;
            if (!visited[nextX][nextY] && grid[nextX][nextY] === 1) {
                visited[nextX][nextY] = true
                m = dfs(grid, visited, nextX, nextY,m+1)
            }
        }
        return m
    }

    let  max = 0

    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[i].length; j++) {
            if (!visited[i][j] && grid[i][j] === 1) {
                // Depth First Search
                visited[i][j] = true;
                let m = dfs(grid, visited, i, j, 1);
                if (m > max) max = m;
            }
        }
    }
    return max
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

# Go

DSF: Version One

var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
var count int = 0

func maxAreaOfIsland(grid [][]int) int {
    res := 0
    visited := make([][]bool, len(grid))
    for i := 0; i < len(grid); i++ {
        visited[i] = make([]bool, len(grid[0]))
    }

    for i, rows := range grid {
        for j, v := range rows {
            if v == 1 && !visited[i][j] {
                // First version, reset count, there must be one
                count = 1
                dfs(grid, visited, i, j)
                res = max(res, count)
            }

        }
    }

    return res
}

// First version
func dfs(grid [][]int, visited [][]bool, i, j int) {
    visited[i][j] = true // Mark as visited
    for _, d := range DIRECTIONS {
        x, y := i+d[0], j+d[1]
        if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
            continue
        }
        if grid[x][y] == 1 && !visited[x][y] {
            count++
            dfs(grid, visited, x, y)
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

DFS: Version Two

var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
var count int = 0

func maxAreaOfIsland(grid [][]int) int {
    res := 0
    visited := make([][]bool, len(grid))
    for i := 0; i < len(grid); i++ {
        visited[i] = make([]bool, len(grid[0]))
    }

    for i, rows := range grid {
        for j, v := range rows {
            if v == 1 && !visited[i][j] {
                // Second version
                count = 0
                dfs(grid, visited, i, j)
                res = max(res, count)
            }

        }
    }

    return res
}

// Second version
func dfs(grid [][]int, visited [][]bool, i, j int) {
    if visited[i][j] || grid[i][j] == 0 {
        return
    }
    visited[i][j] = true
    count++
    for _, d := range DIRECTIONS {
        x, y := i+d[0], j+d[1]
        if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
            continue
        }
        dfs(grid, visited, x, y)
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

BFS:

var DIRECTIONS = [4][2]int{{-1, 0}, {0, -1}, {1, 0}, {0, 1}}
var count int = 0

func maxAreaOfIsland(grid [][]int) int {
    res := 0
    visited := make([][]bool, len(grid))
    for i := 0; i < len(grid); i++ {
        visited[i] = make([]bool, len(grid[0]))
    }

    for i, rows := range grid {
        for j, v := range rows {
            if v == 1 && !visited[i][j] {
                count = 0
                bfs(grid, visited, i, j)
                res = max(res, count)
            }

        }
    }

    return res
}

// bfs
func bfs(grid [][]int, visited [][]bool, i, j int) {
    visited[i][j] = true
    count++
    queue := [][2]int{{i, j}}
    for len(queue) > 0 {
        cur := queue[0]
        queue = queue[1:]
        for _, d := range DIRECTIONS {
            x, y := cur[0]+d[0], cur[1]+d[1]
            if x < 0 || x >= len(grid) || y < 0 || y >= len(grid[0]) {
                continue
            }
            if grid[x][y] == 1 && !visited[x][y] {
                count++
                queue = append(queue, [2]int{x, y})
                visited[x][y] = true
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

# Rust

DFS: Version One

impl Solution {
    const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];

    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let mut visited = vec![vec![false; grid[0].len()]; grid.len()];

        let mut res = 0;
        for (i, nums) in grid.iter().enumerate() {
            for (j, &num) in nums.iter().enumerate() {
                if !visited[i][j] && num == 1 {
                    let mut count = 1;
                    visited[i][j] = true;
                    Self::dfs(&grid, &mut visited, (i as i32, j as i32), &mut count);
                    res = res.max(count);
                }
            }
        }

        res
    }

    pub fn dfs(
        grid: &[Vec<i32>],
        visited: &mut [Vec<bool>],
        (x, y): (i32, i32),
        count: &mut i32,
    ) {
        for (dx, dy) in Self::DIRECTIONS {
            let (nx, ny) = (x + dx, y + dy);
            if nx < 0 || nx >= grid.len() as i32 || ny < 0 || ny >= grid[0].len() as i32 {
                continue;
            }
            let (nx, ny) = (nx as usize, ny as usize);
            if !visited[nx][ny] && grid[nx][ny] == 1 {
                visited[nx][ny] = true;
                *count += 1;
                Self::dfs(grid, visited, (nx as i32, ny as i32), count);
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

DFS: Version Two

impl Solution {
    const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];

    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let mut visited = vec![vec![false; grid[0].len()]; grid.len()];

        let mut res = 0;
        for (i, nums) in grid.iter().enumerate() {
            for (j, &num) in nums.iter().enumerate() {
                if !visited[i][j] && num == 1 {
                    let mut count = 0;
                    Self::dfs(&grid, &mut visited, (i as i32, j as i32), &mut count);
                    res = res.max(count);
                }
            }
        }

        res
    }

    pub fn dfs(
        grid: &[Vec<i32>],
        visited: &mut [Vec<bool>],
        (x, y): (i32, i32),
        count: &mut i32,
    ) {
        if visited[x as usize][y as usize] || grid[x as usize][y as usize] == 0 {
            return;
        }
        visited[x as usize][y as usize] = true;
        *count += 1;
        for (dx, dy) in Self::DIRECTIONS {
            let (nx, ny) = (x + dx, y + dy);
            if nx < 0 || nx >= grid.len() as i32 || ny < 0 || ny >= grid[0].len() as i32 {
                continue;
            }
            Self::dfs(grid, visited, (nx, ny), count);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

BFS:

use std::collections::VecDeque;
impl Solution {
    const DIRECTIONS: [(i32, i32); 4] = [(0, 1), (1, 0), (-1, 0), (0, -1)];

    pub fn max_area_of_island(grid: Vec<Vec<i32>>) -> i32 {
        let mut visited = vec![vec![false; grid[0].len()]; grid.len()];

        let mut res = 0;
        for (i, nums) in grid.iter().enumerate() {
            for (j, &num) in nums.iter().enumerate() {
                if !visited[i][j] && num == 1 {
                    let mut count = 0;
                    Self::bfs(&grid, &mut visited, (i as i32, j as i32), &mut count);
                    res = res.max(count);
                }
            }
        }

        res
    }

    pub fn bfs(grid: &[Vec<i32>], visited: &mut [Vec<bool>], (x, y): (i32, i32), count: &mut i32) {
        let mut queue = VecDeque::new();
        queue.push_back((x, y));
        visited[x as usize][y as usize] = true;
        *count += 1;
        while let Some((cur_x, cur_y)) = queue.pop_front() {
            for (dx, dy) in Self::DIRECTIONS {
                let (nx, ny) = (cur_x + dx, cur_y + dy);
                if nx < 0 || nx >= grid.len() as i32 || ny < 0 || ny >= grid[0].len() as i32 {
                    continue;
                }
                let (nx, ny) = (nx as usize, ny as usize);
                if !visited[nx][ny] && grid[nx][ny] == 1 {
                    visited[nx][ny] = true;
                    queue.push_back((nx as i32, ny as i32));
                    *count += 1;
                }
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
Last updated:: 9/4/2025, 3:19:38 PM
Copyright © 2025 keetcoder