K Weakest Rows in a Matrix

Problem

  1. The K Weakest Rows in a Matrix

Solution

  • Uses Binary search to count 1s
  • Uses heap to keep k weakest rows
  • It naturally satisfies the condition for weak rows with the same number of soldiers. The smaller index row is processed first and hence any next row would not get pushed to the heap.
from heapq import heappushpop, heappush, heappop

class Solution(object):
    def countOne(self, row):
        ans = 0
        for n in row:
            if n == 0:
                break
            ans += 1
        return ans
    
    def countOneBS(self, row, start, end):
        if row[start] == 0:
            return 0
        
        if row[end] == 1:
            return end - start + 1
        
        mid = start + (end - start) // 2
        
        # print("mid=", mid, "start=", start, "end=", end)
        return self.countOneBS(row, start, mid) + \
               self.countOneBS(row, mid + 1, end)
    
    
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
        # max heap
        heap = []
        weakestRows = []
        
        for index, row in enumerate(mat):
            c = self.countOneBS(row, 0, len(row) - 1)
            
            if len(heap) == k:
                heappushpop(heap, (-c, -index))
            else:
                heappush(heap,(-c, -index))
                
        while heap:
            weakestRows.append(-heappop(heap)[1])
            
        return weakestRows[::-1]

Reference

BlinkBlank

Knowledge is the seed of wisdom.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.