# LeetCode 讀書會第 41 次聚會 2022/04/19

## leetcode 讀書會通知

1. 項目: 第 41 次聚會
2. 目的: 線上一起寫題目, 由有想法的人帶領, 先解題, 再看該題有趣的解法
3. 時間: 04/19 (二) 20:00 ~ 21:00
4. 地點: google meet 線上 (前 10 分鐘預備鏈接)
5. 解題項目: [Heap](https://leetcode.com/explore/featured/card/heap/643/heap/)
6. 共筆: GitHub https://github.com/programmingbookclub/Leetcode-club
7. 備註:

---

* [done] MEDIUM 215 Kth Largest Element in an Array https://leetcode.com/problems/kth-largest-element-in-an-array
* [done] MEDIUM 347 Top K Frequent Elements https://leetcode.com/problems/top-k-frequent-elements
* EASY 703 Kth Largest Element in a Stream https://leetcode.com/problems/kth-largest-element-in-a-stream
* EASY 1046 Last Stone Weight https://leetcode.com/problems/last-stone-weight
* EASY 1337 The K Weakest Rows in a Matrix https://leetcode.com/problems/the-k-weakest-rows-in-a-matrix
* MEDIUM 378 Kth Smallest Element in a Sorted Matrix https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix
* 🔓 MEDIUM 253 Meeting Rooms II https://leetcode.com/problems/meeting-rooms-ii
* MEDIUM 973 K Closest Points to Origin https://leetcode.com/problems/k-closest-points-to-origin
* 🔓 MEDIUM 1167 Minimum Cost to Connect Sticks https://leetcode.com/problems/minimum-cost-to-connect-sticks
* MEDIUM 1642 Furthest Building You Can Reach https://leetcode.com/problems/furthest-building-you-can-reach
* HARD 295 Find Median from Data Stream https://leetcode.com/problems/find-median-from-data-stream

---

import heapq
class KthLargest:
    # clarification: 
    # only add?
    # upperbound/lowerbound of stream element
    # 
    # idea: minheap with fixed size
    # push the new element into heap, update the heap (if the size is too big), return heap[0]
    # tc:
    # O(nlogn) initialize, best case O(n)
    # O(logn) add, best case O(1)
    # sc:
    # O(k) to store elements of stream
    def __init__(self, k: int, nums: List[int]):
        self.size = k
        self.hp = nums
        heapq.heapify(self.hp)
        while len(self.hp) > k:
            heapq.heappop(self.hp)

    def add(self, val: int) -> int:
        heapq.heappush(self.hp, val)
        if len(self.hp) > self.size:
            heapq.heappop(self.hp)
        return self.hp[0]

import heapq
class Solution:
    def lastStoneWeight(self, stones: List[int]) -> int:
        # idea:
        # use max-heap, (use negative element while inserting into built-in minheap)
        # put the difference back (even diff == 0) until heap size == 1
        hp = [-s for s in stones]
        heapq.heapify(hp)
        
        while len(hp) != 1:
            a = heapq.heappop(hp)
            b = heapq.heappop(hp)
            heapq.heappush(hp, -1*abs(a-b))
        
        return -1*hp[0]

import heapq
class Solution:
    # use maxHeap
    # calculate the sum of each row and store the (row_sum, index) into max_heap
    # if the size is too big, pop out the biggest in the heap
    # if the two biggest has the same sum, pop out the one has bigger index
    # 
    # tc: 
    # O(H*W) to go through the matrix, where H is height and W is width. 
    # O(klogk) to pick out k weakest row index
    #
    # sc:
    # O(k) to store k weakest rows
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        hp = []                                     # store (row_sum, index) in the heap
        for i, row in enumerate(mat):
            x = sum(row)
            heapq.heappush(hp, (-1*x, -1*i))        # both use negative due to built-in minHeap
            if len(hp) > k:
                heapq.heappop(hp)
        
        res = []                # output the answer in order
        while hp:
            ppl, index = heapq.heappop(hp)
            res.append(-1*index)
        
        return res[::-1]

( (v == w) && (i < j) ) || (v < w)

( v == w && i < j ) || v < w