We want to find k-smallest strength row, so we use a size-limited max heap with count of ones as the primary key and row-index as the secondary key. Since in a row 0’s and 1’s are nicely separated, we can use binary search to find the index of the leftmost 0 which is the count of ones.
Time: 
from heapq import heappush as push, heappop as pop
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
# row = [1 1 1 1 0 0 0 0 0]
# row_i < row_j:
# * one_count_i < one_count_j
# * one_count_i == one_count_j and i < j
# max_heap of (one_count, row_index) size limited to k
# (2, 0) (4, 1), (1, 2), (2, 3), (5, 4)
# max_heap: (2, 0) (1, 2)
def count_ones(row):
# [ = 1 | = 0 ]
# lo
n = len(row)
lo, hi = 0, n-1
while lo <= hi:
mid = (lo + hi) // 2
if row[mid] == 0:
hi = mid-1
else:
lo = mid+1
return lo
max_heap = []
for i, row in enumerate(mat):
push(max_heap, (-count_ones(row), -i))
if len(max_heap) > k:
pop(max_heap)
weak_rows = deque()
while max_heap:
weak_rows.appendleft( -pop(max_heap)[1] )
return list(weak_rows)
unreasonably effective 
Leave a comment