Category: top_k
-
LeetCode 1337: The K Weakest Rows in a Matrix
link 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…
-
LeetCode 857: Minimum Cost to Hire K Workers
link If we hire a group of k workers, each worker must be paid at the maximum pay-rate where pay-rate is . Backtrack We can try all k-subsets of workers to find the minimum cost. Time: , space: . Sort and top-k Cost is a product of max-rate and sum-of-qualities. If we did not have…
-
LeetCode 973: K Closest Points to Origin
link k-closest points are the k-smallest distance points. We use a max-heap to keep track of the k-smallest distance points. Time: , space: .
-
LeetCode 767: Reorganize String
link If all characters were distinct, we could put them in any order and it works. For two instances of a repeated character, we need to put a different character in-between. The best choice to put in-between two instances of the most frequent character is the second most frequent character. Because, in that way we…
unreasonably effective 