# HackerRank Coding Questions for Placements – 7

Find the row with maximum number of 1s?

Given a boolean 2D array, where each row is sorted. Find the row with the maximum number of 1s.

```Example
Input matrix
0 1 1 1
0 0 1 1
1 1 1 1  // this row has maximum 1s
0 0 0 0

Output: 2```

A 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. Finally, return the index of row with maximum 1s. The time complexity of this method is O(m*n) where m is number of rows and n is number of columns in matrix.

We can do better. Since 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. The count of 1s will be equal to total number of columns minus the index of first 1.

See the following code for implementation of the above approach.

 `#include ` `#define R 4` `#define C 4` `/* A function to find the index of first index of 1 in a boolean array arr[] */` `int` `first(``bool` `arr[], ``int` `low, ``int` `high)` `{` `  ``if``(high >= low)` `  ``{` `    ``// get the middle index  ` `    ``int` `mid = low + (high - low)/2; ` `    ``// check if the element at middle index is first 1` `    ``if` `( ( mid == 0 || arr[mid-1] == 0) && arr[mid] == 1)` `      ``return` `mid;` `    ``// if the element is 0, recur for right side` `    ``else` `if` `(arr[mid] == 0)` `      ``return` `first(arr, (mid + 1), high);` `    ``else` `// If element is not first 1, recur for left side` `      ``return` `first(arr, low, (mid -1));` `  ``}` `  ``return` `-1;` `}` `// The main function that returns index of row with maximum number of 1s. ` `int` `rowWithMax1s(``bool` `mat[R][C])` `{` `    ``int` `max_row_index = 0, max = -1; ``// Initialize max values` `    ``// Traverse for each row and count number of 1s by finding the index ` `    ``// of first 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;` `}` `/* Driver program to test above functions */` `int` `main()` `{` `    ``bool` `mat[R][C] = { {0, 0, 0, 1},` `        ``{0, 1, 1, 1},` `        ``{1, 1, 1, 1},` `        ``{0, 0, 0, 0}` `    ``};` `    ``printf``(``"Index of row with maximum 1s is %d n"``, rowWithMax1s(mat));` `    ``return` `0;` `}`

Output:

`Index of row with maximum 1s is 2`

Time Complexity: O(mLogn) where m is a number of rows and n is a number of columns in a matrix.