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.

---

package javabypatel;

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.

Given an array of integers. All numbers occur thrice except one number which occurs once. Find the number in O(n) time & constant extra space. 

Count number of Bits to be flipped to convert A to B 

Count number of Set Bits in Integer. 

Check if number is Power of Two. 

Find all subsets of a set (Power Set). 

Skyline Problem in Java. 

Find Minimum length Unsorted Subarray, Sorting which makes the complete array sorted 

Count trailing zeros in factorial of a number 

When to use SOAP over REST Web Service. Is REST better than SOAP? 

Tower Of Hanoi Program in Java. 

Enjoy !!!! 

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