Count number of ones in a matrix in increasing order

I have this island program that just displays the number of possible islands in a matrix.

I have a matrix of 1's and 0's I want to get group of 1's in row wise, column wise and diagonal wise. This program count the number of possibilities and returns 5 as output for below input.

 { 1, 0, 0, 1, 0 }, 
{ 1, 0, 1, 0, 0 }, 
{ 0, 0, 1, 0, 1 }, 
{ 1, 0, 1, 0, 1 } 

But I need output as island sizes in increasing order as 1 2 2 4

How to achieve this?

Explanation: a) last row first column has single island, b) first row 1st column, 2nd row 1st column and has island of size 2. c) 3rd row last column, last row last column has island of size 2. d) 1st row 4th column, remaining rows 3rd column has size of 4.

public class Islands {
// No of rows and columns
static final int ROW = 4, COL = 5;
// A function to check if a given cell (row, col) can
// be included in DFS
static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
// row number is in range, column number is in range
// and value is 1 and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix.
// It only considers the 8 neighbors as adjacent vertices
static void DFS(int M[][], int row, int col, boolean visited[][]) {
// These arrays are used to get row and column numbers
// of 8 neighbors of a given cell
int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns count of islands in a given
// boolean 2D matrix
static int countIslands(int M[][]) {
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
boolean visited[][] = new boolean[ROW][COL];
// Initialize count as 0 and travese through the all cells
// of given matrix
int count = 0;
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i][j] == 1 && !visited[i][j]) // If a cell with
{ // value 1 is not
// visited yet, then new island found, Visit all
// cells in this island and increment island count
DFS(M, i, j, visited);
++count;
}
return count;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception {
int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
System.out.println("Number of islands is: " + countIslands(M));
}
}

Make following changes to solve it:

• Add static variable size to count size for each island.
• Replace count by listSizes to store the size of each island. New island's size is added to this list.
• Invoke the method (renamed from countIslands to sizeIslands) to get final listSizes.
• Sort the list before printing it out.

Final code:

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Islands {
// No of rows and columns
static final int ROW = 4, COL = 5;
static int size;
// A function to check if a given cell (row, col) can
// be included in DFS
static boolean isSafe(int M[][], int row, int col, boolean visited[][]) {
// row number is in range, column number is in range
// and value is 1 and not yet visited
return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
}
// A utility function to do DFS for a 2D boolean matrix.
// It only considers the 8 neighbors as adjacent vertices
static void DFS(int M[][], int row, int col, boolean visited[][]) {
// These arrays are used to get row and column numbers
// of 8 neighbors of a given cell
int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
// Mark this cell as visited
visited[row][col] = true;
size++;
// Recur for all connected neighbours
for (int k = 0; k < 8; ++k)
if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
DFS(M, row + rowNbr[k], col + colNbr[k], visited);
}
// The main function that returns size of islands in a given
// boolean 2D matrix
static List<Integer> sizeIslands(int M[][]) {
// Make a bool array to mark visited cells.
// Initially all cells are unvisited
boolean visited[][] = new boolean[ROW][COL];
// Initialize empty list and travese through the all cells
// of given matrix
List<Integer> listSizes = new ArrayList<Integer>();
for (int i = 0; i < ROW; ++i)
for (int j = 0; j < COL; ++j)
if (M[i][j] == 1 && !visited[i][j]) // If a cell with
{ // value 1 is not
// visited yet, then new island found, Visit all
// cells in this island and increment island count
size = 0;
DFS(M, i, j, visited);
listSizes.add(size);
}
return listSizes;
}
// Driver method
public static void main(String[] args) throws java.lang.Exception {
int M[][] = new int[][] { { 1, 0, 0, 1, 0 }, { 1, 0, 1, 0, 0 }, { 0, 0, 1, 0, 1 }, { 1, 0, 1, 0, 1 } };
List<Integer> list = sizeIslands(M);
Collections.sort(list);
System.out.println("Sizes of islands are: " + list);
}