Find row with maximum no. of 1s

The problem, simply

You get a grid with m rows and n columns that holds only 0s and 1s. In every row, all the 0s come first and all the 1s come after them. So each row is sorted.

Give back the number of the row that has the most 1s. If two rows tie, give the one closer to the top. If there are no 1s at all, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Count the 1s in every row, and remember the row with the biggest count.

1. For each row, add up its numbers. Because they are only 0s and 1s, the sum is the number of 1s.
2. If the sum is bigger than the best so far, this row is the new best. Use bigger, not bigger or equal, so that ties keep the earlier row.

class Solution {
    public int rowWithMax1s(int[][] matrix) {
        int bestRow = -1, bestCount = 0;
        for (int r = 0; r < matrix.length; r++) {
            int count = 0;
            for (int value : matrix[r]) count += value;   // 0s add nothing, 1s add one
            if (count > bestCount) {                       // strictly bigger keeps the earlier row on ties
                bestCount = count;
                bestRow = r;
            }
        }
        return bestRow;
    }
}

How long it takes: we read every cell, O(m*n). Extra room: two counters, O(1). It never uses the fact that the 1s are packed at the right end.

Way 2: the clever way

Do what the teacher did. Keep one finger, starting at the top right corner.

1. Start at row = 0, col = n - 1.
2. If the cell is a 1, this row has at least n - col ones, which beats every row before. Write it down as the best row, and move left.
3. If the cell is a 0, this row cannot beat the best, because it would need a 1 right here. Move down to the next row, same column.
4. Stop when you go off the left side or off the bottom.

The column never moves right again. That is the whole trick: once a row has reached column c, later rows only matter if they reach further left than c.

class Solution {
    public int rowWithMax1s(int[][] matrix) {
        if (matrix.length == 0 || matrix[0].length == 0) return -1;
        int m = matrix.length, n = matrix[0].length;
        int bestRow = -1;
        int col = n - 1;                          // the finger starts at the top right

        for (int row = 0; row < m && col >= 0; row++) {
            while (col >= 0 && matrix[row][col] == 1) {
                col--;                            // a 1: this row is winning, look further left
                bestRow = row;
            }
            // a 0 (or the left edge): this row is done, go down to the next one
        }
        return bestRow;
    }
}

How long it takes: the finger moves left at most n times and down at most m times, so O(m + n). Extra room: O(1).

Another way: binary search in each row

If you need the count for every row, or the rows arrive one at a time, find the first 1 in each row with binary search. The number of ones is n minus that position.

class Solution {
    public int rowWithMax1s(int[][] matrix) {
        int bestRow = -1, bestCount = 0;
        for (int r = 0; r < matrix.length; r++) {
            int n = matrix[r].length;
            int lo = 0, hi = n - 1, first = n;    // first = n means no 1 in this row
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (matrix[r][mid] == 1) { first = mid; hi = mid - 1; }   // a 1, but maybe an earlier one exists
                else lo = mid + 1;
            }
            if (n - first > bestCount) { bestCount = n - first; bestRow = r; }
        }
        return bestRow;
    }
}

This takes O(m log n) time. It beats Way 1, and it beats Way 2 only when there are very few rows and very many columns.

Watch out for

• No 1s anywhere: the answer is -1, not 0.
• Ties: Way 2 keeps the top row on its own, because a later row needs a 1 further left to take over. In Way 1, use > and not >=.
• Resetting col to n - 1 for each row turns Way 2 back into O(m*n). The finger never moves right.
• Rows that are not sorted. Then none of the tricks work and you must count, O(m*n).

What interviewers ask next

• Row with the most 0s? Mirror the walk. Start at the top left, move right on a 0 (and make this row the best), move down on a 1.
• What if rows are sorted the other way, 1s first? Start at the top left corner and move right on a 1, down on a 0.
• Return the count, not the row. It is n - 1 - col when the walk ends, or n minus the first 1 position of the best row.
• Can you do better than O(m + n)? Not in the worst case for a square grid: each row may need one look, and the 1s boundary can move one step each row.
• What if you only need to know whether some row is all 1s? Check matrix[r][0] == 1 for every row, O(m).

Remember this

Grown-up words: the sticker sheets are a binary matrix with sorted rows, the finger walk is a staircase search, and finding the first 1 with halving is a lower bound binary search.