- Write a program to find a row having maximum number of 1's in a row wise sorted boolean matrix.

Given a matrix of size M x N having 0 and 1. Each row of input matrix is sorted from left to right. We have to **find a row having maximum number of 1's**.

For Example:

Input Matrix: 0, 1, 1, 1 0, 0, 1, 1 0, 0, 1, 1 1, 1, 1, 1 Output : Row number 3 contains maximum number of 1

**Method 1 : By counting number of 1's in every row**

Let inputMatrix be a boolean integer matrix of size R X C.

- Traverse input matrix row wise and count the number of 1's in every row.
- If the number of 1's in current row is more than the maximum count found till now then update maximum count.
- At last, print the row number having maximum count of 1.

**Method 2 : Using Modified Binary Search**

Let inputMatrix be a boolean integer matrix of size R X C.

- As each row of matrix is sorted, we just need to find the index of first 1(left most 1) to get the count of all 1's in a row. Let the index of left most 1 is i, then total number of 1's in that row is C - i.
- We will use a modified binary search algorithm to find the left most instance of 1.
- Using this approach we can find the number of 1's in any row in log(C) time instead of O(C).
- If the number of 1's in current row is more than the maximum count found till now then update maximum count.
- At last, print the row number having maximum count of 1.

## C program to find row having maximum number of 1 using binary search

#include <stdio.h> #define COLS 4 #define ROWS 4 /* Returns the index of first occurence of K in sorted array. If is not present then it returns -1. It uses a customized binary search algorithm */ int getFirstIndex(int *array, int left, int right, int K) { int mid; if (right >= left) { /* Get mid index */ mid = (left + right)/2; /* if array[mid] == K, then mid will be the index of first occurence of K if either mid == 0, or array[mid-1] < K */ if ((array[mid] == K) && (mid == 0 || K > array[mid-1])) /* first occurence found */ return mid; else if (K > array[mid]) /* Recursively search on right sub array */ return getFirstIndex(array, (mid + 1), right, K); else /* Recursively search on left sub array */ return getFirstIndex(array, left, (mid - 1), K); } return -1; } /* Returns the index of row having maximum number of 1's in matrix */ int getMaxOneRowIndx(int matrix[ROWS][COLS]) { int i, firstIndex, rowMax = 0, max = 0; /* As all rows are sorted, Find the index of first one in every row(Index), and then number of 1's is equal to COLS - Index. Return the index of row hacing maximum number of 1 */ for (i = 0; i < ROWS; i++) { firstIndex = getFirstIndex(matrix[i], 0, COLS-1, 1); if(firstIndex != -1 && (COLS-firstIndex) > max) { max = COLS - firstIndex; rowMax = i; } } return rowMax; } int main() { int matrix[ROWS][COLS] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {0, 0, 1, 1}, {1, 1, 1, 1} }; printf("Maximum number of 1's is in row %d\n", getMaxOneRowIndx(matrix)); return 0; }Output

Maximum number of 1's is in row 3

**Method 3 : Fastest approach having O(R + C) time complexity**

Let inputMatrix be a boolean integer matrix of size R X C. ro

- As each row of matrix is sorted from left to right, all 1's are grouped together in right side of a row.
- Let the index of left most 1 in max one count row found till now is i.
- We will first check whether current row(r
^{th}row) contains more 1's than max one count row found till now. If yes, then we will process current row otherwise skip it. - If matrix[r][i] == 0, then skip this row.
- Else traverse r
^{th}row toward left side from index i till we find left most 1.

#include <stdio.h> #define COLS 4 #define ROWS 4 /* Returns the index of row having maximum number of 1's in matrix */ int getMaxOneRowIndx(int matrix[ROWS][COLS]) { int i, firstIndex, rowMax; /* Initialize rowMax to 0 and firstIndex to COLS */ rowMax = 0; firstIndex = COLS; for(i = 0; i < ROWS; i++){ while(firstIndex > 0 && matrix[i][firstIndex-1] == 1){ firstIndex--; rowMax = i; } } return rowMax; } int main() { int matrix[ROWS][COLS] = { {0, 1, 1, 1}, {0, 0, 1, 1}, {1, 1, 1, 1}, {0, 0, 0, 1} }; printf("Maximum number of 1's is in row %d\n", getMaxOneRowIndx(matrix)); return 0; }Output

Maximum number of 1's is in row 2