4. Find row with maximum number of 1's

4. Find row with maximum number of 1's

Problem link :- click here

package progams;

import java.util.Scanner;

public class Matrix__4
{

	/*
        	Given a boolean 2D matrix of   r x c dimensions where each row is sorted.
        	We have to find the row with max number of 1's
        	
        	each row is sorted.
        	1) first find the index of first 1 in the first row by binary search.
        	2) do the binary search with        low -> 0       high -> index of first 1 in previous row - 1
        */
        
        static int rowWithMaxOnes(int mat[][], int r, int c)
        {
        	int index_of_first1 = binarySearch(mat[0], 0, c-1);
        	int row_with_max1 = 0;
        	
        	for(int i=1; i<r; i++)
        	{
        		int temp = binarySearch(mat[i], 0, index_of_first1-1);
        		
        		if(index_of_first1  >  temp)
        		{
        			//we want the smallest index_of_first1
        			index_of_first1 = temp;
        			row_with_max1 = i;
        		}
        	}
        	
        	return row_with_max1;
        }
        
        static int binarySearch(int arr[], int low, int high)
        {
        	while(low<=high)
        	{
        		int mid = (low+high)/2;
        		
        		if(arr[mid] == 1)
        			high = mid - 1;
        		else
        			low = mid + 1;
        	}
        	return low;
        }
	
	public static void main(String[] args)
	{
		int i, j, r, c;
		
		Scanner s = new Scanner(System.in);
		System.out.print("Enter the number of rows : ");
		r = s.nextInt();
		System.out.print("Enter the numvber of columns : ");
		c = s.nextInt();
		int matrix[][] = new int[r][c];
		System.out.println("Enter the elements of the matrix : ");
		for(i=0; i<r; i++)
		{
			for(j=0; j<c; j++)
				matrix[i][j] = s.nextInt();
		}
		System.out.println("Given matrix : ");
		printMatrix(matrix, r, c);

		int ans = rowWithMaxOnes(matrix, r, c);
		System.out.println("\n\nRow with maximum number of 1's : " + ans);
	}

	static void printMatrix(int mat[][], int r, int c)
	{
		for(int i=0; i<r; i++)
		{
			for(int j=0; j<c; j++)
				System.out.print(mat[i][j] + "  ");
			System.out.println();
		}
	}
}

Time complexity :- O(r+c)
Space complexity :- O(1)