Max Area of Island
Program for having Max Area of Island
You are given a grid represented as a matrix where each cell is either 0 (water) or 1 (land).
An island is a group of 1’s connected horizontally or vertically. The grid edges are surrounded by water.
The area of an island is the count of cells within it. Return the largest island area in the grid. If no islands exist, return 0.
Example 1:
Input: grid = [
[0,1,1,0,1],
[1,0,1,0,1],
[0,1,1,0,1],
[0,1,0,0,1]
]
Output: 6
[0,1,1,0,1],
[1,0,1,0,1],
[0,1,1,0,1],
[0,1,0,0,1]
]
Output: 6
Explanations :
- 1’s cannot be connected diagonally, so the maximum area of the island is 6.
Constraints:
- 1 <= grid.length, grid[i].length <= 50
Solution for having Max Area of Island
Recommendation for Time and Space Complexity – Aim for O(m * n) time and space complexity, where m is the number of rows and n is the number of columns.
Hints for solving problems
Hint 1
An island is a group of connected 1’s. Can you find all such groups by visiting each only once, perhaps using recursion?
Hint 2
Use Depth First Search (DFS) to explore each group. Start from a 1 and recursively visit all connected 1’s. How can you calculate the island’s area during this?
Hint 3
Traverse the grid. When you find a 1, start a DFS, mark visited cells as 0, and count the area. After each DFS, update the maximum area. Return the largest area after checking the entire grid.
There are mainly 3 approach to solve this problem-
- Depth First Search Method
- Breadth First Search Method
- Disjoint Set Union Method
1. Depth First Method
This approach uses recursion to explore all connected 1’s starting from a cell. By marking visited cells as 0, it calculates the area of an island while traversing the grid.
- Time complexity: O(m * n)
- Space complexity: O(m * n)
where m is the number of rows and n is the number of columns in the grid.
Code
C++
Java
Python
JavaScript
C++
class Solution {
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ROWS = grid.size(), COLS = grid[0].size();
int area = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == 1) {
area = max(area, dfs(grid, r, c));
}
}
}
return area;
}
int dfs(vector<vector<int>>& grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.size() ||
c >= grid[0].size() || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int res = 1;
for (int i = 0; i < 4; i++) {
res += dfs(grid, r + directions[i][0],
c + directions[i][1]);
}
return res;
}
};
Java
public class Solution {
private static final int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public int maxAreaOfIsland(int[][] grid) {
int ROWS = grid.length, COLS = grid[0].length;
int area = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == 1) {
area = Math.max(area, dfs(grid, r, c));
}
}
}
return area;
}
private int dfs(int[][] grid, int r, int c) {
if (r < 0 || c < 0 || r >= grid.length ||
c >= grid[0].length || grid[r][c] == 0) {
return 0;
}
grid[r][c] = 0;
int res = 1;
for (int[] dir : directions) {
res += dfs(grid, r + dir[0], c + dir[1]);
}
return res;
}
}
Python
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
visit = set()
def dfs(r, c):
if (r < 0 or r == ROWS or c < 0 or
c == COLS or grid[r][c] == 0 or
(r, c) in visit
):
return 0
visit.add((r, c))
return (1 + dfs(r + 1, c) +
dfs(r - 1, c) +
dfs(r, c + 1) +
dfs(r, c - 1))
area = 0
for r in range(ROWS):
for c in range(COLS):
area = max(area, dfs(r, c))
return area
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
maxAreaOfIsland(grid) {
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const ROWS = grid.length, COLS = grid[0].length;
const dfs = (r, c) => {
if (r < 0 || c < 0 || r >= ROWS ||
c >= COLS || grid[r][c] === 0) return 0;
grid[r][c] = 0;
let res = 1;
for (const [dr, dc] of directions) {
res += dfs(r + dr, c + dc);
}
return res;
};
let area = 0;
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (grid[r][c] === 1) {
area = Math.max(area, dfs(r, c));
}
}
}
return area;
}
}
2. Breadth First Search Method
This method uses a queue to iteratively explore all connected 1’s layer by layer. It calculates the island’s area while marking cells as visited during the traversal.
- Time complexity: O(m*n)
- Space complexity: O(m*n)
where m is the number of rows and n is the number of columns in the grid.
Code
C++
Java
Python
JavaScript
C++
class Solution {
int directions[4][2] = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ROWS = grid.size(), COLS = grid[0].size();
int area = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == 1) {
area = max(area, bfs(grid, r, c));
}
}
}
return area;
}
int bfs(vector<vector<int>>& grid, int r, int c) {
queue<pair<int, int>> q;
grid[r][c] = 0;
q.push({r, c});
int res = 1;
while (!q.empty()) {
auto node = q.front();q.pop();
int row = node.first, col = node.second;
for (int i = 0; i < 4; i++) { int nr = row + directions[i][0]; int nc = col + directions[i][1]; if (nr >= 0 && nc >= 0 && nr < grid.size() &&
nc < grid[0].size() && grid[nr][nc] == 1) {
q.push({nr, nc});
grid[nr][nc] = 0;
res++;
}
}
}
return res;
}
};
Java
public class Solution {
private static final int[][] directions = {{1, 0}, {-1, 0},
{0, 1}, {0, -1}};
public int maxAreaOfIsland(int[][] grid) {
int ROWS = grid.length, COLS = grid[0].length;
int area = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) {
if (grid[r][c] == 1) {
area = Math.max(area, bfs(grid, r, c));
}
}
}
return area;
}
private int bfs(int[][] grid, int r, int c) {
Queue<int[]> q = new LinkedList<>();
grid[r][c] = 0;
q.add(new int[]{r, c});
int res = 1;
while (!q.isEmpty()) {
int[] node = q.poll();
int row = node[0], col = node[1];
for (int[] dir : directions) {
int nr = row + dir[0], nc = col + dir[1];
if (nr >= 0 && nc >= 0 && nr < grid.length &&
nc < grid[0].length && grid[nr][nc] == 1) {
q.add(new int[]{nr, nc});
grid[nr][nc] = 0;
res++;
}
}
}
return res;
}
}
Python
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]
ROWS, COLS = len(grid), len(grid[0])
area = 0
def bfs(r, c):
q = deque()
grid[r][c] = 0
q.append((r, c))
res = 1
while q:
row, col = q.popleft()
for dr, dc in directions:
nr, nc = dr + row, dc + col
if (nr < 0 or nc < 0 or nr >= ROWS or
nc >= COLS or grid[nr][nc] == 0
):
continue
q.append((nr, nc))
grid[nr][nc] = 0
res += 1
return res
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
area = max(area, bfs(r, c))
return area
JavaScript
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
maxAreaOfIsland(grid) {
const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];
const ROWS = grid.length, COLS = grid[0].length;
let area = 0;
const bfs = (r, c) => {
const q = new Queue();
q.push([r, c]);
grid[r][c] = 0;
let res = 1;
while (!q.isEmpty()) {
const [row, col] = q.pop();
for (const [dr, dc] of directions) {
const nr = row + dr, nc = col + dc;
if (nr >= 0 && nc >= 0 && nr < ROWS &&
nc < COLS && grid[nr][nc] === 1) {
q.push([nr, nc]);
grid[nr][nc] = 0;
res++;
}
}
}
return res;
};
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) {
if (grid[r][c] === 1) {
area = Math.max(area, bfs(r, c));
}
}
}
return area;
}
}
3. Disjoint Set Union Method
This approach treats the grid as a graph and uses the Union-Find technique to group connected 1’s into sets. The size of the largest set gives the maximum island area.
- Time complexity: O(m * n).
- Space complexity: O(m * n).
where m is the number of rows and n is the number of columns in the grid.
Code
C++
Java
Python
JavaScript
C++
class DSU {
vector<int> Parent, Size;
public:
DSU(int n) {
Parent.resize(n + 1);
Size.resize(n + 1);
for (int i = 0; i <= n; i++) { Parent[i] = i; Size[i] = 1; } } int find(int node) { if (node != Parent[node]) { Parent[node] = find(Parent[node]); } return Parent[node]; } bool unionBySize(int u, int v) { int pu = find(u); int pv = find(v); if (pu == pv) return false; if (Size[pu] >= Size[pv]) {
Size[pu] += Size[pv];
Parent[pv] = pu;
} else {
Size[pv] += Size[pu];
Parent[pu] = pv;
}
return true;
}
int getSize(int node) {
return Size[find(node)];
}
};
class Solution {
public:
int maxAreaOfIsland(vector<vector<int>>& grid) {
int ROWS = grid.size();
int COLS = grid[0].size();
DSU dsu(ROWS * COLS);
int directions[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int area = 0;
auto index = [&](int r, int c) {
return r * COLS + c;
};
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) { if (grid[r][c] == 1) { for (auto& d : directions) { int nr = r + d[0]; int nc = c + d[1]; if (nr >= 0 && nc >= 0 && nr < ROWS &&
nc < COLS && grid[nr][nc] == 1) {
dsu.unionBySize(index(r, c), index(nr, nc));
}
}
area = max(area, dsu.getSize(index(r, c)));
}
}
}
return area;
}
};
Java
public class DSU {
private int[] Parent, Size;
public DSU(int n) {
Parent = new int[n + 1];
Size = new int[n + 1];
for (int i = 0; i <= n; i++) { Parent[i] = i; Size[i] = 1; } } public int find(int node) { if (node != Parent[node]) { Parent[node] = find(Parent[node]); } return Parent[node]; } public boolean union(int u, int v) { int pu = find(u); int pv = find(v); if (pu == pv) return false; if (Size[pu] >= Size[pv]) {
Size[pu] += Size[pv];
Parent[pv] = pu;
} else {
Size[pv] += Size[pu];
Parent[pu] = pv;
}
return true;
}
public int getSize(int node) {
return Size[find(node)];
}
}
public class Solution {
public int maxAreaOfIsland(int[][] grid) {
int ROWS = grid.length;
int COLS = grid[0].length;
DSU dsu = new DSU(ROWS * COLS);
int[][] directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int area = 0;
for (int r = 0; r < ROWS; r++) {
for (int c = 0; c < COLS; c++) { if (grid[r][c] == 1) { for (int[] d : directions) { int nr = r + d[0]; int nc = c + d[1]; if (nr >= 0 && nc >= 0 && nr < ROWS &&
nc < COLS && grid[nr][nc] == 1) {
dsu.union(r * COLS + c, nr * COLS + nc);
}
}
area = Math.max(area, dsu.getSize(r * COLS + c));
}
}
}
return area;
}
}
Python
class DSU:
def __init__(self, n):
self.Parent = list(range(n + 1))
self.Size = [1] * (n + 1)
def find(self, node):
if self.Parent[node] != node:
self.Parent[node] = self.find(self.Parent[node])
return self.Parent[node]
def union(self, u, v):
pu = self.find(u)
pv = self.find(v)
if pu == pv:
return False
if self.Size[pu] >= self.Size[pv]:
self.Size[pu] += self.Size[pv]
self.Parent[pv] = pu
else:
self.Size[pv] += self.Size[pu]
self.Parent[pu] = pv
return True
def getSize(self, node):
par = self.find(node)
return self.Size[par]
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
ROWS, COLS = len(grid), len(grid[0])
dsu = DSU(ROWS * COLS)
def index(r, c):
return r * COLS + c
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
area = 0
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == 1:
for dr, dc in directions:
nr, nc = r + dr, c + dc
if (nr < 0 or nc < 0 or nr >= ROWS or
nc >= COLS or grid[nr][nc] == 0
):
continue
dsu.union(index(r, c), index(nr, nc))
area = max(area, dsu.getSize(index(r, c)))
return area
JavaScript
class DSU {
constructor(n) {
this.Parent = Array(n + 1).fill(0).map((_, i) => i);
this.Size = Array(n + 1).fill(1);
}
/**
* @param {number} node
* @return {number}
*/
find(node) {
if (this.Parent[node] !== node) {
this.Parent[node] = this.find(this.Parent[node]);
}
return this.Parent[node];
}
/**
* @param {number} u
* @param {number} v
* @return {boolean}
*/
union(u, v) {
let pu = this.find(u);
let pv = this.find(v);
if (pu === pv) return false;
if (this.Size[pu] >= this.Size[pv]) {
this.Size[pu] += this.Size[pv];
this.Parent[pv] = pu;
} else {
this.Size[pv] += this.Size[pu];
this.Parent[pu] = pv;
}
return true;
}
/**
* @param {number} node
* @return {number}
*/
getSize(node) {
return this.Size[this.find(node)];
}
}
class Solution {
/**
* @param {number[][]} grid
* @return {number}
*/
maxAreaOfIsland(grid) {
const ROWS = grid.length;
const COLS = grid[0].length;
const dsu = new DSU(ROWS * COLS);
const directions = [
[1, 0], [-1, 0], [0, 1], [0, -1]
];
let area = 0;
const index = (r, c) => r * COLS + c;
for (let r = 0; r < ROWS; r++) {
for (let c = 0; c < COLS; c++) { if (grid[r][c] === 1) { for (let [dr, dc] of directions) { let nr = r + dr, nc = c + dc; if (nr >= 0 && nc >= 0 && nr < ROWS &&
nc < COLS && grid[nr][nc] === 1) {
dsu.union(index(r, c), index(nr, nc));
}
}
area = Math.max(area, dsu.getSize(index(r, c)));
}
}
}
return area;
}
}
