Counting 1's in a 2D array of 1's and 0's with O(n) complexity
15:52 20 Oct 2022

Assume a 2D [n][n] matrix of 1's and 0's. All the 1's in any row should come before 0's. The number of 1's in any row i should be at least the number of 1's row i+1. Find a method and write a Java program with O(n) complexity to count the 1'sin the array.

For example we have the following array:

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

I have written a code that counts the 1's correctly but I am not sure if the complexity is O(n) or O(n^2).

The code is the following:

public class SpecialMatrix {

    public static void main(String[] args) {
        int[][] a = {{1,1,1,1},
                     {1,1,1,1},
                     {1,1,0,0},
                     {1,0,0,0}};
        
        int n = 4;
        int cnt=0;
        int row; 
        int col = 0;
        for (row = n-1; row>=0; row--)
        {
            while(col

The output looks like this:

Row: 3 Col: 0 Cnt: 4

Row: 2 Col: 1 Cnt: 7

Row: 1 Col: 2 Cnt: 9
Row: 1 Col: 3 Cnt: 11


11

I would like some help regarding the complexity of the code. Is it O(n) or O(n^2)?

Thanks!

java arrays algorithm