Soft suave technologies program questions and answers
Round 3:
Max Area of Island
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.
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
1.Traverse the 2D grid a perform DFS traversal from each of the cells containing 1.
2.Mark the current cell as visited by changing the cell value to 0.
3.The area of the island starting from the current cell is 1.
4.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).
5.After traversal is complete return the area obtained.
6.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.
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;
}
JAVA
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));
}
}
Comments
Post a Comment