### 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

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

Do following for every row after the first row:

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

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;
}
```