Problem¶

You are given an m x n binary matrix mat of 1’s (representing soldiers) and 0’s (representing civilians). The soldiers are positioned in front of the civilians. That is, all the 1’s will appear to the left of all the 0’s in each row.

A row i is weaker than a row j if one of the following is true:

• The number of soldiers in row i is less than the number of soldiers in row j.
• Both rows have the same number of soldiers and i < j.

Return the indices of the k weakest rows in the matrix ordered from weakest to strongest.

Example 1:

Input: mat =

[[1,1,0,0,0],
 [1,1,1,1,0],
 [1,0,0,0,0],
 [1,1,0,0,0],
 [1,1,1,1,1]], 

• Row 0: 2
• Row 1: 4
• Row 2: 1
• Row 3: 2
• Row 4: 5
  The rows ordered from weakest to strongest are [2,0,3,1,4].

Example 2:

Input: mat =

[[1,0,0,0],
 [1,1,1,1],
 [1,0,0,0],
 [1,0,0,0]], 

• Row 0: 1
• Row 1: 4
• Row 2: 1
• Row 3: 1
  The rows ordered from weakest to strongest are [0,2,3,1].

Constraints:

• m == mat.length
• n == mat[i].length
• 2 <= n, m <= 100
• 1 <= k <= m
• matrix[i][j] is either 0 or 1.

Solve¶

White board¶

First glance:

• It a matrix, the normal calculation sum total soldiers each row can cost up to n, we can use binary search to reduce the needed calculation to log(n)
• We need to sort each row total soldiers right after to get k weakest, we can use any sort function and worst case will be k = n, which we need the whole list sorted as the return value

So:

• The calculate for count each row soldier cost O(n log n)
• The sort cost O(n log n)

Implement, all build-in python¶

Bisect + Sort¶

O(n log n)

Python provided some level of frequently use list operation, which have sort, and binary search

• I have bisect for binary search on list: bisect right find the insert point at right most position in a small -> large sorted order list. Here we have reverse order (eg [1,1,0,0]) list, so I need to use a modification x -> -x. All is stored in count array
• I have sort and sortKey to sort array : Instead of sorting the count directly, I create a new index array index, and sort on the index list directly by the value of count instead.

class Solution:

    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        def sortKey(x):
            return -x

        count = [bisect_left(r, 0, key = sortKey) for r in mat]
        # print(count)
        index = list(range(len(mat)))

        def sortKey(x):
            return count[x]

        index.sort(key = sortKey)
        return [i for i in index[:k]]

Sum + sort¶

O(n ** 2)

Just sum each round instead, which cost O(n ** 2)

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        count = [sum(r) for r in mat]
        index = list(range(len(mat)))
        def sortKey(x):
            return count[x]
        index.sort(key = sortKey)
        return [i for i in index[:k]]