Question

link

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