Find the number of Islands

Count number of islands where every island is row-wise and column-wise separated


Count total number of islands present in given matrix where every island is separated row-wise and column-wise.

Given a rectangular matrix which has only two values ‘1’ and ‘0’.
1 represents land.
0 represents water.
Islands are all rectangular in shape that is values ‘1’ will always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘0’s.

If there is any diagonal island then it will be considered adjacent islands and will be separate.
Count total number of islands in the given matrix.


Lets understand what is the input and the expected output.

Sample 1:
Input: 
        int[][] island = new int[][] {
            { 0,  0,  0 },
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 0,  0,  1 },
            { 0,  0,  1 },
            { 1,  1,  0 }               
        };
Output: 3

Sample 2:
Input:
        int[][] island = new int[][] {
            { 1,  0,  0 },
            { 0,  1,  0 },
            { 0,  0,  1 },
            { 0,  1,  0 },
            { 1,  0,  0 },
            { 0,  1,  0 }               
        };

Output:6

Sample 3:
Input:
        int[][] island = new int[][] {
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 1,  1,  0 },
            { 0,  1,  0 },
            { 0,  0,  1 },
            { 1,  1,  1 }               
        };

Output:3

Algorithm


We can solve the problem by using BFS and DFS approach but the problem is even simple and can be done in O(M*N) and constant extra space.

As all islands are perfect rectangular and separated by at least one line of ‘0’s, It is sure that first element of islands(rectangle) will definitely have LEFT coordinate and TOP coordinate '0' and all other elements of same island will definitely have either Left or Top coordinate.

So just count all the first element of island and we are done.


Java Program to find the number of Islands.


public class CountNumberOfIsland {
 public static void main(String[] args) {
  
  int[][] island = new int[][] {
   {1, 0, 0},
   {0, 1, 0},
   {0, 0, 1},
   {0, 1, 0},
   {1, 0, 0},
   {0, 1, 0}    
  };
  System.out.println(countIsland(island));
 }

 public static int countIsland(int[][] island){
  int count=0;
  
  for (int i = 0; i < island.length; i++) {
   for (int j = 0; j < island[i].length; j++) {
     
    if(island[i][j] == 1){

     //check top and left coordinate
     if( (i-1 < 0 || island[i-1][j] == 0) && (j-1 < 0 || island[i][j-1] == 0) ){
      count++;
     }
    }
    
   } 
  }
  return count;
 }
}


You may also like to see


Find the number of Islands using DFS.



Enjoy !!!! 

If you find any issue in post or face any error while implementing, Please comment.

Post a Comment