LeetCode 1341. The K Weakest Rows in a Matrix
Question
Given a m * n
matrix mat
of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k
weakest rows in the matrix ordered from the weakest to the strongest.
A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.
Example
1 | Input: mat = |
Solution
We need to maintain the number of soldiers and each row, and then ascending by the count. Also, we can use the priority queue to reduce the time complexity for sorting because we just need to maintain k size. In addition, the question gives us the condition, which means all 1s show before than 0s, so we can use binary search for optimizing.
Code
1 | // time:O(nlogm) space:O(n), n = # of rows, m = # of cols. |