EasyNo. 1337
The K Weakest Rows in a Matrix — LeetCode 1337 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Array, Binary Search, Matrix, Sorting, Heap (Priority Queue)
- Reading time
- 2 min
- Source
- leetcode.com
The 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.
Example
- Input
- mat =
- Output
- [2,0,3]
- Explanation
- The number of soldiers in each row is:
Python solution
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
m, n = len(mat), len(mat[0])
ans = [n - bisect_right(row[::-1], 0) for row in mat]
idx = list(range(m))
idx.sort(key=lambda i: ans[i])
return idx[:k]Complexity
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1337. The K Weakest Rows in a Matrix is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 0778 | Swim in Rising Water | Hard |
| 1268 | Search Suggestions System | Medium |
| 1439 | Find the Kth Smallest Sum of a Matrix With Sorted Rows | Hard |
| 1631 | Path With Minimum Effort | Medium |
| 1648 | Sell Diminishing-Valued Colored Balls | Medium |
Frequently asked questions
- How hard is LeetCode 1337. The K Weakest Rows in a Matrix?
LeetCode 1337. The K Weakest Rows in a Matrix is rated Easy on LeetCode.
- What topics does LeetCode 1337. The K Weakest Rows in a Matrix cover?
LeetCode 1337. The K Weakest Rows in a Matrix is tagged Array, Binary Search, Matrix, Sorting and Heap (Priority Queue) on LeetCode.