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

Reference :- 
http://www.geeksforgeeks.org/count-number-islands-every-island-separated-line/

Problem statement :- 

Given a rectangular matrix which has only two possible values ‘X’ and ‘O’. The values ‘X’ always appear in form of rectangular islands and these islands are always row-wise and column-wise separated by at least one line of ‘O’s. Note that islands can only be diagonally adjacent. Count the number of islands in the given matrix.

Examples:

mat[M][N] =  {{'O', 'O', 'O'},
              {'X', 'X', 'O'},
              {'X', 'X', 'O'},
              {'O', 'O', 'X'},
              {'O', 'O', 'X'},
              {'X', 'X', 'O'}
             };
Output: Number of islands is 3

mat[M][N] =  {{'X', 'O', 'O', 'O', 'O', 'O'},
              {'X', 'O', 'X', 'X', 'X', 'X'},
              {'O', 'O', 'O', 'O', 'O', 'O'},
              {'X', 'X', 'X', 'O', 'X', 'X'},
              {'X', 'X', 'X', 'O', 'X', 'X'},
              {'O', 'O', 'O', 'O', 'X', 'X'},
             };
Output: Number of islands is 4

My approach :-

The article mentions straightforward option to find-out the number of rectangles. This has complexity of O(mn).




If we are allowed to use a little more memory we can take different approach.

Here we traverse row by row. As soon as we come across a "X" we find out all the boundaries of that island and save it in a list. 




When in next row we come across other "X" we can check if it falls under already considered island. In that case we do not need to check columns which fall in that rectangle. We can directly jump to column outside islands. 




This way we can skip some iterations. Also at the end we get list of all rectangle. Which is an added advantage.




Java implementation 

Also shared at http://ideone.com/IlpH9t 








package matrix;




import java.util.ArrayList;




public class RectangularIslands {




 public static void main(String[] args) {

  char[][] mat1   =  

       {{'O', 'O', 'O'},

             {'X', 'X', 'O'},

             {'X', 'X', 'O'},

             {'O', 'O', 'X'},

             {'O', 'O', 'X'},

             {'X', 'X', 'O'}

            };

 findIslands(mat1);

 

  char[][] mat2 =  

        {{'X', 'O', 'O', 'O', 'O', 'O'},

               {'X', 'O', 'X', 'X', 'X', 'X'},

               {'O', 'O', 'O', 'O', 'O', 'O'},

               {'X', 'X', 'X', 'O', 'X', 'X'},

               {'X', 'X', 'X', 'O', 'X', 'X'},

               {'O', 'O', 'O', 'O', 'X', 'X'},

              };

  findIslands(mat2);

  

  char[][] mat3 =

      {{'X', 'O', 'O', 'O', 'O', 'O'},

               {'O', 'O', 'X', 'O', 'X', 'X'},

               {'O', 'O', 'O', 'O', 'O', 'O'},

               {'X', 'O', 'X', 'O', 'X', 'X'},

               {'X', 'O', 'X', 'O', 'X', 'X'},

               {'O', 'O', 'O', 'O', 'X', 'X'},

              };

  findIslands(mat3);

  

  char[][] mat4 =

     {{'X', 'X', 'X', 'X', 'X', 'X'},

   {'X', 'X', 'X', 'X', 'X', 'X'},

   {'X', 'X', 'X', 'X', 'X', 'X'},

   {'X', 'X', 'X', 'X', 'X', 'X'},

   {'X', 'X', 'X', 'X', 'X', 'X'},

   {'X', 'X', 'X', 'X', 'X', 'X'},

           };

 findIslands(mat4);




 }

 

 

 public static ArrayList<RectangularIslands.Island> islandList;

 public static void findIslands(char[][] matrix) {

  islandList = new ArrayList<RectangularIslands.Island>();

  

  int i=0,j=0;

  int matrixRows = matrix.length;

  int matrixCols = matrix[0].length;

  

  while(i<matrixRows){

   j=0;

   while(j<matrixCols){

    if(matrix[i][j] =='X'){

     // Check if this position is already considered in previously observed island

     Island notedIsland =  isInIsland(i,j);

     if(notedIsland!=null){

      // point is already in noted island. So directly jump to position outside island

      j=notedIsland.endPointColnum+1;

     }else{

      int startPointRownum = i;

      int startPointColnum = j;

      j++;

      // We have found top-left corner of island. Now find the boundaries

      while(j<matrixCols && matrix[i][j]=='X'){

       j++; // Keep moving right till we find X or end of matrix

      }

      int endPointColnum = j-1; // Current j points to 'O' or matrix boundry

     

      // Find the bottom of island 

      int k=i;

      while(k+1<matrixRows && matrix[k+1][startPointColnum]=='X'){

       // Keep moving right till we find X or end of matrix

       k++;

      }

      int endPointRownum = k;

     

      // Create rectangle object and add to list

      Island ilnd = new Island();

      ilnd.startPointRownum=startPointRownum;

      ilnd.startPointColnum=startPointColnum;

      ilnd.endPointRownum=endPointRownum;

      ilnd.endPointColnum=endPointColnum;

      islandList.add(ilnd);

     }

    }else{

     j++;

    }

   }

   i++;

  }

  

  System.out.println("No of islands ="+islandList.size());

 }

 static private class Island{

  public int startPointRownum,startPointColnum,endPointRownum,endPointColnum;

 }

 

 public static Island isInIsland(int rownum, int colnum){

  for(Island ilnd:islandList){

   if(ilnd.startPointRownum<=rownum && ilnd.startPointColnum<=colnum && ilnd.endPointRownum>=rownum && ilnd.endPointColnum>=colnum){

    return ilnd;

   }

  }

  return null;

 }




}



Output :- 


No of islands =3

No of islands =4

No of islands =6

No of islands =1