## Given a matrix(2D array) containing binary digits with each row sorted, this function will find the row which as maximum number of 1’s .

### Example

**INPUT:**

0 1 1 1

0 0 1 1

0 1 1 1

1 1 1 1

**OUTPUT:**

3

In the above example, third row contains maximum number of 1’s ie, four 1’s

**Time Complexity: O(mlogn),**

where m is the number of rows and n is the number of columns

In this method, the main idea is to do binary search in each row and find the index where 1 has occured for the first time. The output is the row which has the least index value.

## Algorithm

**1.** Traverse through all the rows in the matrix

**2.** For each row, do binary search and find the index of the first occurrence of the 1 in that row

Binary search

a. If the mid element is 1 and mid-1 element is 0 then return mid index

b. If the mid element is 0, then do binary search on the right half ie, from mid+1 to n

c. else, do binary search on left half ie, from 0 to mid-1.

**3.** Return the row which has the least index.

## C++ Program

#include <bits/stdc++.h> #include <climits> #define m 4 #define n 4 using namespace std; //This function will return the index of the first one using binary search int firstoneIndex(int arr[], int low, int high) { if (low <= high) { int mid = low + (high - low)/2; if ((mid==0 || arr[mid -1]==0) && arr[mid]==1) { return mid; } else if(arr[mid]==0) { return firstoneIndex(arr, (mid+1), high); } else { return firstoneIndex(arr,low, (mid-1)); } } return -1; } //In this function we will compare all indexes of first one //we will print the row which has the least index int maxOnes(int arr[m][n]) { int row = 0; int index = INT_MAX; for (int i = 0; i < m; ++i) { int first_index = firstoneIndex(arr[i],0,n-1); if (first_index != -1 && first_index<index) { index = first_index; row = i; } } cout<<"The row having maximum ones is "<<row<<endl; } int main() { int arr[m][n] = {{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,1,1,1}}; maxOnes(arr); return 0; }

**Time Complexity: O(m+n)**

## Algorithm

**1.** Traverse through all the rows in the matrix

**2.** Start from the right corner element in the first row, go left until you find a 0 and go to next row until you find a 1.

**3.** return the last row that you encounter.

## C++ Program

#include <bits/stdc++.h> #define m 4 #define n 4 using namespace std; //In this function, we will go left until we find a 0 ie, j=j-1 //go to next row until we find a 1 int maxOnes(int arr[m][n]) { int row = 0; int index = INT_MAX; int j = n -1 ; for (int i = 0; i < m; ++i) { while(arr[i][j]==1 && j>=0) { j= j-1; row = i; } } cout<<"The row having maximum ones is "<<row<<endl; } int main() { int arr[m][n] = {{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,1,1,1}}; maxOnes(arr); return 0; }