Question

Find the row with maximum number of 1s in java ?

int arr[][] = {   {0,0,1,1},

                      {0,0,0,1},

                      {1,1,1,1},

                      {0,0,0,0}

              };

Result:- 2 row

Answer 1

A very simple method is to do a row wise traversal of the matrix, count the number of 1s in each row and compare the count with max. And returns the index of row which having maximum 1s.

The time complexity of Following method is O(m*n) where m is number of rows and n is number of columns.

    //Time complexity O(r*c)
    //Where r is number of rows and c is number of columns in matrix
    private static int getRowNumber(int[][] arr, int r, int c) {
        int max=0, row=-1;
        for(int i=0; i<r; i++) {
            int count1s = 0;
            for(int j=0; j<c; j++) {
                if(arr[i][j]==1) {
                    count1s++;
                }
            }
            if(count1s > max) {
                max = count1s;
                row = i;
            }
        }
        return row;
    }

Output:-

2 row has maximum 1s

Answer 2

Now, i am going to give your a better approach. Please see the approach, the Time Complexity: O(mLogn). Each row is sorted, we can use Binary Search to count of 1s in each row. We find the index of first instance of 1 in each row. And count of 1s will be equal to total number of columns minus the index of first 1.

See the code for find the row with maximum number 1s:-

//Time Complexity: O(mLogn) 

//Where m is number of rows and n is number of columns

private static int getRowNumberWithMax1s(int[][] arr, int R, int C) {

int max_row_index = 0, max = -1;  

// Traverse for each row and count number of 1s to find the index of first 1 

int i, index; 

for (i = 0; i < R; i++) { 

index = first(arr[i], 0, C - 1); 

    if (index != -1 && C - index > max) { 

max = C - index; 

max_row_index = i; 

    } 

}

return max_row_index;

}

private static int first(int arr[], int low, int high) { 

if (high >= low) { 

    // Get middle index 

    int mid = low + (high - low) / 2; 

    // Check if an element at middle index is first 1 

    if ((mid == 0 || (arr[mid - 1] == 0)) && arr[mid] == 1) 

return mid; 

    // If an element is 0, recur for right side 

    else if (arr[mid] == 0) 

return first(arr, (mid + 1), high);    

    // If an element is not first 1, recur for left side 

    else 

return first(arr, low, (mid - 1)); 

} 

return -1; 

} 

Output:-

2 row has maximum 1s