CC-10 : Find island with maximum area.

Description:

Given an adjacency matrix filled with Os and 1s. An island is a collection of cells sharing cell boundary in North-South-East-West with other cells with value 1, or sharing boundary with North-South-East-West boundary of matrix. Diagonal touching is not considered as boundary connection. Find the island with greatest area from within the adjacency matrix.

Test cases and expected outputs:

Input Parameters	Expected outputs
Matrix : 1,0,0,1, 0,0,0,0, 0,0,1,1, 0,0,1,1,	Max area island: 4
Matrix : 1,0,0,1, 0,1,1,0, 0,0,0,0, 1,0,0,0,	Max area island: 2

Pseudocode:

findIslandsMaxArea(int[][] matrix) method:

Initialize a variable named maxArea to store the max area of islands found.

Iterate through vertices of matrix using a for loop with iIdx as loop variable with values from 0 to count of matrix.length:

Iterate through vertices of matrix using a for loop with jIdx as loop variable with values from 0 to count of matrix[0].length:

Set variable currArea to return value of call to findIslandsMaxAreaDfs(matrix,iIdx,jIdx).

If currArea > maxArea, set maxArea to currArea.

Return maxArea.

checkPath() method:

Initialize a variable named totalArea to store the max area of adjacent islands found.

While i and j are within index limits of matric and matrix[i][j]==1:

Set matrix[i][j]=0.

Set areaTop int variable to value return by recursive call to findIslandsMaxAreaDfs(matrix,i+1,j).

Set areaBottom int variable to value return by recursive call to findIslandsMaxAreaDfs(matrix,i-1,j).

Set areaRight int variable to value return by recursive call to findIslandsMaxAreaDfs(matrix,i,j+1).

Set areaLeft int variable to value return by recursive call to findIslandsMaxAreaDfs(matrix,i,j-1).

Set totalArea to sum of areaTop, areaBottom, areaRight, areaLeft.

Return totalArea.

Code:

public class GraphFindIslandMaxArea {

public int findIslandsMaxAreaDfs(int[][] matrix, int i, int j){
	int totalArea=0;
	while  ((i >= 0 ) && (i < matrix.length)
			&& (j >= 0 ) &&(j < matrix[0].length) 
			&& (matrix[i][j] == 1)){
		matrix[i][j]=0;
		int areaTop=findIslandsMaxAreaDfs(matrix, i+1, j);
		int areaBottom=findIslandsMaxAreaDfs(matrix, i-1, j);
		int areaRight=findIslandsMaxAreaDfs(matrix, i, j+1);
		int arealeft=findIslandsMaxAreaDfs(matrix, i, j-1);
		totalArea=areaTop+areaBottom+areaRight+arealeft+1;
	}
	return totalArea;
}

public int findIslandsMaxArea(int[][] matrix) {
	int maxArea=0;
	for(int iIdx=0; iIdx < matrix.length; iIdx++){
        for(int jIdx=0; jIdx < matrix[0].length;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   int currArea=findIslandsMaxAreaDfs(matrix, iIdx, jIdx);
        	   if (currArea > maxArea) {
        		   maxArea=currArea;
        	   }
            }
        }
    } 
	return maxArea;
}

Click here to download and run code and test cases !

Below fully running code can be copied and run on Eclipse or other Java IDEs. Refer the classname in code below. If the class name below is "A", save the code below to a file named A.java before running it. Be sure to try your own test cases to enhance your understanding ! You can also tweak the code to optimize or add enhancements and custom features.

public class GraphFindIslandMaxArea {

public int findIslandsMaxAreaDfs(int[][] matrix, int i, int j){
	int totalArea=0;
	while  ((i >= 0 ) && (i < matrix.length)
			&& (j >= 0 ) &&(j < matrix[0].length) 
			&& (matrix[i][j] == 1)){
		matrix[i][j]=0;
		int areaTop=findIslandsMaxAreaDfs(matrix, i+1, j);
		int areaBottom=findIslandsMaxAreaDfs(matrix, i-1, j);
		int areaRight=findIslandsMaxAreaDfs(matrix, i, j+1);
		int arealeft=findIslandsMaxAreaDfs(matrix, i, j-1);
		totalArea=areaTop+areaBottom+areaRight+arealeft+1;
	}
	return totalArea;
}

public int findIslandsMaxArea(int[][] matrix) {
	int maxArea=0;
	for(int iIdx=0; iIdx < matrix.length; iIdx++){
        for(int jIdx=0; jIdx < matrix[0].length;jIdx++){
           if (!(matrix[iIdx][jIdx]==0)){
        	   int currArea=findIslandsMaxAreaDfs(matrix, iIdx, jIdx);
        	   if (currArea > maxArea) {
        		   maxArea=currArea;
        	   }
            }
        }
    } 
	return maxArea;
}

public static void print2dArray(int[][] intArray, String label) throws Exception {
	// Case 1: The input Array is null !!
    if (intArray == null) { System.out.println("\n\n Input 2d Array was null !! \n"); return; }
    // Case 2: Print input Array by index (first to last)
	System.out.println();
	System.out.println("***********************************************************************");
	System.out.print(label+" : \n");
	int rIdx=0; int cIdx=0;
	for (rIdx=0; rIdx < intArray.length; rIdx++) {
		for (cIdx=0; cIdx < intArray[rIdx].length; cIdx++) {
			System.out.print(intArray[rIdx][cIdx]);
			if (cIdx < intArray[rIdx].length) System.out.print(",");
		}
		System.out.print("\n");
	} 
	System.out.println();
	System.out.println("************************************************************************");
	System.out.println();
	Thread.sleep(2000);
	return;
}


public static void main(String[] args) {
	/***********************
	 Test cases given below:
	 **********************/
	int retVal;
	try {
	GraphFindIslandMaxArea gph=new GraphFindIslandMaxArea();
	int[][] matrix = {	{1,0,0,1},
						{0,0,0,0},	
						{0,0,1,1},
						{0,0,1,1}};
	print2dArray(matrix, "Matrix" );
	retVal=gph.findIslandsMaxArea(matrix);
	System.out.println("Max area island: "+ retVal);
	
	gph=new GraphFindIslandMaxArea();
	int[][] matrix1 = {	{1,0,0,1},
						{0,0,0,0},	
						{0,0,0,1},
						{1,0,1,1}};
	print2dArray(matrix1, "Matrix" );
	retVal=gph.findIslandsMaxArea(matrix1);
	System.out.println("Max area island: "+ retVal);
	
	gph=new GraphFindIslandMaxArea();
	int[][] matrix2 = {	{1,0,0,1},
						{0,1,1,0},	
						{0,0,0,0},
						{1,0,0,0}};
	print2dArray(matrix2, "Matrix" );
	retVal=gph.findIslandsMaxArea(matrix2);
	System.out.println("Max area island: "+ retVal);
	
	
	}catch (Exception exception) {
		System.out.print("Exception: "+ exception);
		exception.printStackTrace();
	}
		
}



}