# [Question] Find Row With Most 1s

### Question

Given a 2D array with only 1s and 0s, where each row is sorted.

Find the row with the maximum number of 1s. 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

### Analysis

By using a modified version of binary search, we can achieve a O(mLogn) solution where m is number of rows and n is number of columns in matrix.

However, there’s better solution that works in linear time!

### Solution

1. Get the index of first (or leftmost) 1 in the first row.

2. Do following for every row after the first row:

1. IF the element on left of previous leftmost 1 is 0, ignore this row.

2. ELSE Move left until a 0 is found. Update the leftmost index to this index and max_row_index to be the current row.

The time complexity is O(m+n).

### Code

written by me

``````public int solution(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int p = n;
int row = -1;
for (int i = 0; i < m; i++) {
// now p is larger than 0, otherwise it's already terminated
if (matrix[i][p - 1] == 0) {
continue;
}
// p points to a 1, now search to the left direction
for (int j = p - 1; j >= 0; j--) {
if (matrix[i][j] == 1) {
p = j;
} else {
break;
}
}
// p have a new value now
if (p == 0) {
return i;
} else {
row = i;
}
}
return row;
}
``````