Problem Description: Given a 2D matrix, the matrix has only 0(representing water) and 1(representing land) as entries. An island in the matrix is formed by grouping all the adjacent 1’s connected 4-directionally(horizontal and vertical). Find the maximum area of the island in the matrix. Assume that all four edges of the grid are surrounded by water.
Note: The area of an island group is the number of cells in that island group.
Table of Contents
Example
Input 1:
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,1,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,1,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: Area of largest island = 12
Input 2:
Grid = {{0,1,0,0,1,1,0},
{0,0,0,0,1,0,0},
{0,0,0,1,1,0,0},
{0,0,1,1,0,0,0}}
Output: Area of largest island = 7
Consider the first input example given above. Given below is the representation of the above 2D grid, the cells representing land are marked as 1 (colored as green) and cells representing water are marked 0 (colored in blue).
As observed from the diagram, 5 island groups are formed. The largest island group has been outlined in red while the smaller island groups are outlined in yellow. The area of the largest island group is 12 units.
Note: it should be noted that the island groups are formed by connecting grid cells in horizontal (right & left) and vertical(up and down) directions (and not in diagonal directions).
Types of Solution for Max Area of Island
- Depth First Search
- Breadth First Search
Depth First Search
Approach for Max Area of Island
We aim to calculate the area of the largest island by visiting recursively all the neighbors (and neighbors of these neighbors) of cells that contain 1. This recursive traversal to neighbors and neighbors of the neighbors is achieved by performing DFS. While performing DFS we recursively increase the total area visited by 1 for every new cell (containing 1’s only) visited.
Algorithm for Max Area of Island
- Traverse the 2D grid a perform DFS traversal from each of the cells containing 1.
- Mark the current cell as visited by changing cell value to 0.
- The area of the island starting from the current cell is 1.
- Recursively visit all the neighbors (up-right-down-left) of current cells that contain 1, mark these neighbors as visited, and also increase the area by 1 for every valid neighbor (cells with value 1) visited(by changing cell value to 0).
- After traversal is complete return the area obtained.
- Perform steps 2,3,4 and 5 for each of the cells (of the matrix) containing 1 and return a maximum of all the area values obtained.
Consider the example grid given above: we start from the left-most and top-most cell of the largest island that has value 1 (by now, all the cells above and left of this cell have already been visited) and perform DFS traversal.
DFS traversal visits cells up to the largest depth, possible in a particular direction. The direction of traversal starting from a particular cell is in the following order: up-right-down-left. The DFS traversal algorithm from the top-most and left-most cell of the largest island is depicted below :
The cells which have been visited in the largest island, have been marked rad.
As we observe, the number of cells traversed during the traversal is 12. Therefore, the area of the largest island is 12.
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// function to perform DFS in four directions(up-right-down-left)
int dfs(vector<vector<int>>& grid, int row, int col)
{
int m = grid.size();
int n = grid[0].size();
/* since the current cell has value = 1
minimum area we start with is 1*/
int area = 1;
/* since you have already visited the current cell
mark it as already visited */
grid[row][col] = 0;
/* used for traversing in four directions(up-right-down-left)*/
vector<int> dir({-1,0,1,0,-1});
/* we begin our traversal into four directions from the current cell*/
for (int i = 0; i < 4; i++)
{
int r = row+dir[i], c = col+dir[i+1];
/* make traversals only when next cell lies within the matrix and is unvisited*/
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1)
area += dfs(grid, r, c);
}
/* total number of cells with value 1 visited from the current cell */
return area;
}
/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
int m = grid.size();
int n = grid[0].size();
/* stores the area of largest consecutive 1's*/
int maxArea = 0;
/* visit each cell of the matrix*/
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
/* begin your traversal from the cell which has value as 1(land)*/
if (grid[i][j] == 1)
/* store the largest area*/
maxArea = max(maxArea, dfs(grid, i, j));
return maxArea;
}
/* main function to implement above function */
int main()
{
vector<vector<int>> 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,1,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,1,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}};
cout<<"Area of largest island = "<<largestIsland(grid);
return 0;
}Area of largest island = 12
Java Program
import java.util.*;
import java.io.*;
class tutorialCup
{
// function to perform DFS in four directions(up-right-down-left)
static int dfs(int grid[][], int row, int col)
{
int m = grid.length;
int n = grid[0].length;
/* since the current cell has value = 1
minimum area we start with is 1*/
int area = 1;
/* since you have already visited the current cell
mark it as already visited */
grid[row][col] = 0;
/* used for traversing in four directions(up-right-down-left)*/
int [] dir = {-1,0,1,0,-1};
/* we begin our traversal into four directions from the current cell*/
for (int i = 0; i < 4; i++)
{
int r = row+dir[i], c = col+dir[i+1];
/* make traversals only when next cell lies within the matrix and is unvisited*/
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1)
area += dfs(grid, r, c);
}
/* total number of cells with value 1 visited from the current cell */
return area;
}
/* function that returns area of largest island */
static int largestIsland(int grid[][])
{
int m = grid.length;
int n = grid[0].length;
/* stores the area of largest consecutive 1's*/
int maxArea = 0;
/* visit each cell of the matrix*/
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
/* begin your traversal from the cell which has value as 1(land)*/
if (grid[i][j] == 1)
/* store the largest area*/
maxArea = Math.max(maxArea, dfs(grid, i, j));
return maxArea;
}
/* main function to implement above function */
public static void main (String[] args)
{
int 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,1,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,1,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}};
System.out.print("Area of largest island = "+largestIsland(grid));
}
}Area of largest island = 12
Complexity Analysis for Max Area of Island
- Time Complexity: T(n) = O(R*C), we traverse each cell of the matrix exactly once.
- Space Complexity: A(n) = O(R*C), since we haven’t used another matrix space that keeps track of whether a particular cell has been visited or not, we simply modify the grid values so that visited cells are marked as visited.
Breadth First Search
Approach for Max Area of Island
We aim to calculate the area of the largest island by visiting Iteratively all the neighbors (and neighbors of these neighbors) of cells that contain 1. This iterative traversal to neighbors and neighbors of the neighbors is achieved by performing BFS. While performing BFS we iteratively increase the total area visited by 1 for every new cell (containing 1’s only) visited.
Algorithm for Max Area of Island
- Traverse the 2D grid a perform BFS traversal from each of the cells containing 1.
- Mark the current cell as visited by changing cell value to 0.
- The area of the island starting from the current cell is 1.
- Iteratively visit all the neighbors (up-right-down-left) of current cells that contain 1, mark these neighbors as visited, and also increase the area by 1 for every valid neighbor (cells with value 1) visited(by changing cell value to 0).
- After traversal is complete return the area obtained.
- Perform steps 2,3,4 and 5 for each of the cells (of the matrix) containing 1 and return a maximum of all the area values obtained.
Consider the example grid given above: we start from the left-most and top-most cell of the largest island that has value 1 (by now, all the cells above and left of this cell have already been visited) and perform BFS traversal.
BFS traversal first visits all the neighbor cells (up-right-down-left) of a particular cell and then iteratively visits neighbors of these neighbors. The BFS traversal algorithm from the top-most and left-most cell of the largest island is depicted below :
The cells which have been visited in the largest island, have been marked red.
As we observe, the number of cells traversed during the traversal is 12. Therefore, the area of the largest island is 12.
Implementation
C++ Program
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// function to perform BFS in four directions(up-right-down-left)
int bfs(vector<vector<int>>& grid, int row, int col)
{
int m = grid.size();
int n = grid[0].size();
/* since the current cell has value = 1
minimum area we start with is 1*/
int area = 1;
/* create a queue to be used in BFS*/
queue<pair<int,int>> q;
/* push the current cell */
q.push({row, col});
/* since you have already visited the current cell
mark it as already visited */
grid[row][col] = 0;
/* used for traversing in four directions(up-right-down-left)*/
vector<int> dir({-1,0,1,0,-1});
/* begin BFS traversal */
while (!q.empty())
{
/* pop a cell with containing 1(land) */
int y = q.front().first, x = q.front().second;
q.pop();
/* we begin our traversal into four directions from the current cell*/
for (int i = 0; i < 4; i++)
{
int r = y+dir[i], c = x+dir[i+1];
/* make traversals only when next cell lies within the matrix and is unvisited*/
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1)
{
/* mark next cell as visited, increase the visited area and push next cells into the queue*/
grid[r][c] = 0;
area++;
q.push({r,c});
}
}
}
/* total number of cells with value 1 visited from the current cell */
return area;
}
/* function that returns area of largest island */
int largestIsland(vector<vector<int>> grid)
{
int m = grid.size();
int n = grid[0].size();
/* stores the area of largest consecutive 1's*/
int maxArea = 0;
/* visit each cell of the matrix*/
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
/* begin your traversal from the cell which has value as 1(land)*/
if (grid[i][j] == 1)
/* store the largest area*/
maxArea = max(maxArea, bfs(grid, i, j));
return maxArea;
}
/* main function to implement above function */
int main()
{
vector<vector<int>> 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,1,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,1,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}};
cout<<"Area of largest island = "<<largestIsland(grid);
return 0;
}Area of largest island = 12
Java Program
import java.util.*;
import java.io.*;
class tutorialCup
{
/* define pair class to handle 2D co-ordinates in a matrix*/
static class pair
{
int row;
int col;
pair(int y,int x)
{
row = y;
col = x;
}
}
// function to perform DFS in four directions(up-right-down-left)
static int dfs(int grid[][], int row, int col)
{
int m = grid.length;
int n = grid[0].length;
/* since the current cell has value = 1
minimum area we start with is 1*/
int area = 1;
/* create a queue to be used in BFS*/
Queue<pair> q = new LinkedList<pair>();
/* push the current cell */
q.add(new pair(row, col));
/* since you have already visited the current cell
mark it as already visited */
grid[row][col] = 0;
/* used for traversing in four directions(up-right-down-left)*/
int [] dir = {-1,0,1,0,-1};
/* begin BFS traversal */
while (!q.isEmpty())
{
/* pop a cell with containing 1(land) */
pair p = q.remove();
int y = p.row, x = p.col;
/* we begin our traversal into four directions from the current cell*/
for (int i = 0; i < 4; i++)
{
int r = y+dir[i], c = x+dir[i+1];
/* make traversals only when next cell lies within the matrix and is unvisited*/
if (r >= 0 && r < m && c >= 0 && c < n && grid[r][c] == 1)
{
/* mark next cell as visited, increase the visited area and push next cells into the queue*/
grid[r][c] = 0;
area++;
q.add(new pair(r,c));
}
}
}
/* total number of cells with value 1 visited from the current cell */
return area;
}
/* function that returns area of largest island */
static int largestIsland(int grid[][])
{
int m = grid.length;
int n = grid[0].length;
/* stores the area of largest consecutive 1's*/
int maxArea = 0;
/* visit each cell of the matrix*/
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
/* begin your traversal from the cell which has value as 1(land)*/
if (grid[i][j] == 1)
/* store the largest area*/
maxArea = Math.max(maxArea, dfs(grid, i, j));
return maxArea;
}
/* main function to implement above function */
public static void main (String[] args)
{
int 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,1,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,1,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}};
System.out.print("Area of largest island = "+largestIsland(grid));
}
}Area of largest island = 12
Complexity Analysis for Max Area of Island
- Time Complexity: T(n) = O(R*C), we traverse each cell of the matrix exactly once.
- Space Complexity : A(n) = O(R*C). since we haven’t used another matrix space that keeps track of whether a particular cell has been visited or not, we simply modify the grid values so that visited cells are marked as visited.