Count number of ones in a matrix in increasing order

Question

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));
    }
}

Answer 1

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);
    }