Нахождение строки с наибольшим числом единиц в упорядоченной бинарной матрице

Условие

Дана квадратная матрица N×N, заполненная нулями и единицами. В каждой строке все нули находятся слева, а после первой единицы в строке дальше идут только единицы. Требуется за минимальное время определить индекс строки, содержащей максимальное количество единиц.

Пример матрицы:

matrix = [
    [0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 0, 1, 1],
    [0, 0, 0, 1, 1, 1],
    [0, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 1],
    [0, 0, 0, 1, 1, 1]
]

Ответ

Достаточно пройти матрицу сверху вниз, сдвигая указатель столбца только влево при встрече единиц. Для примера результат 4; сложность O(строки + столбцы), для квадратной матрицы — O(N).

Код для строк вида 0…01…1:

def best_row(matrix):
    if not matrix or not matrix[0]:
        return -1
    column = len(matrix[0]) - 1
    best = 0
    for index, row in enumerate(matrix):
        while column >= 0 and row[column] == 1:
            column -= 1
            best = index
    return best

В условии пример 7×6, не N×N; алгоритм подходит и ему. При одинаковом количестве единиц сохраняется первая строка. Для непустой матрицы только из нулей выбирается 0. Нельзя применять этот проход к неупорядоченным строкам.