Find Row with maximum number of 1’s in Java

April 30, 2022

Row with maximum number of 1’s in Java

Here, in this page we will discuss the program to find row with maximum number of 1’s in Java Programming Language. We are given a row-wise sorted matrix of size r*c, We will discuss two different ways in this page.

Method Discussed :

Method 1 : Naive Method
Method 2 : Using Binary Search.

Let’s discuss both methods in brief,

Method 1 :

In this method we will traverse each row of the matrix,
Find the count of 1’s in each row.
Then compare it with max_count and the index value.
After complete iteration, print the value of index.

Time and Space Complexity :

Time-Complexity : O(r*c)
Space-Complexity : O(1)

Method 1 : Code in Java

Run

import java.io.*;
 
class Main {
   
   
    public static void main(String[] args)
    {
        int mat[][] = { { 0, 0, 0, 1 },
                        { 0, 1, 1, 1 },
                        { 1, 1, 1, 1 },
                        { 0, 0, 0, 0 } };
                        
        int max_count=0, index=-1;

        for(int i=0; i<4; i++){
        
            int count = 0;
        
            for(int j=0; j<4; j++){
            
                if(mat[i][j]==1) 
                    count++; 
            
            } 
            if(count>max_count){
                max_count = count;
                index = i;
            }
        }

        System.out.println("Index of row with maximum 1s is " +index);
    }
}

Output :

Index of row with maximum 1s is 2

Method 2 :

In this method we will use the concept of binary search.

Time and Space Complexity :

Time-Complexity : O(r*log(c))
Space-Complexity : O(1)

Method 1 : Code in Java

Run

import java.util.*;
 
class Main {
 
    static int R = 4 ;
    static int C  = 4 ;
 

    static int first(int arr[], int low, int high)
    {
        if(high >= low)
        {
            int mid = low + (high - low)/2;
     
            if ( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)
                return mid;
     
            else if (arr[mid] == 0)
                return first(arr, (mid + 1), high);
         
            else
                return first(arr, low, (mid -1));
        }
        return -1;
    }
 
    static int rowWithMax1s(int mat[][])
    {
    
        int max_row_index = 0, max = -1;
 
        int i, index;
        for (i = 0; i < R; i++) { index = first (mat[i], 0, C-1); if (index != -1 && C-index > max)
            {
                max = C - index;
                max_row_index = i;
            }
        }
 
        return max_row_index;
    }
 
    
    public static void main(String[] args) {
         
    int mat[][] = { {0, 0, 0, 1},
                    {0, 1, 1, 1},
                    {1, 1, 1, 1},
                    {0, 0, 0, 0}};
 
    System.out.print("Index of row with maximum 1s is " + rowWithMax1s(mat));
 
    }
}

Output :

Index of row with maximum 1s is 2