leetcode-kth-classical

215. Kth Largest Element in an Array.py

class Solution:
    """
    Thought Process:
        Sorting
        PQ:
        if k == n:
            we return min elememnt 
        So we use a pq with size k to maintain a top k elements out of n.
        after looping over all elements in the given array. Return the topmost one, the smallest one inside the pq with size k, which is kth largest elememnt
    
    Time Complexity Analysis
        Our pq at most has k elements so each time we insert or pop take O(log k)
        and we'll have at most n times pop or insert.
        So, time complexity is O(nlogk)
        
        QuickSelct:
            to find the top k smallest using partititon 3 group
            [...pivot...]
            n-k小的element=第k大
            
            [1,2,3] 
            n=3, k=1
            在第一大(k=1)的element左邊要有2(n-k)個element.
            n=3, k=2
            在第二大(k=2)的element左邊要有1(n-k)個element.
            
            On average, we can have O(n). In worst case, we pick up max element as the pivot, then O(n^2)
    Note:
        python's PQ is min-heap
    """
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        PQ
        O(n log k)
        """
        heap = []
        for n in nums:
            heapq.heappush(heap, n)
            if len(heap) > k:
                heapq.heappop(heap)
        
        return heap[0]
    
    def findKthLargest(self, nums: List[int], k: int) -> int:
        """
        quick select
        
        """
        n = len(nums)
        return self.quickselect(nums, 0, n-1, n-k) # fin number where there're n-k elements smaller on the left side of the number, which mean our ans is kth-largest element
         
    def quickselect(self, nums, start, end, k):
        """
        return k th largest element in the array
        T: O(n)
        
        Geometric sequence:
        T = n + n * (1/2) + n *(1/2) ^2 + n * (1/2) ^ logn
          = n(1+...(1/2) ^ logn)
          = n ( 1 - 1/2)/ (1- 1/2)
          = n
        S: O(log n) because of recursion stack.
        """
        #pivot = nums[start + (end-start) // 2]
        pivot = nums[randint(start, end)]
        l, r = self.partition(nums, start, end, pivot)
        if l<=k<=r:
            return nums[k]
        if l > k:
            return self.quickselect(nums, start, l-1, k)
        if r < k:
            return self.quickselect(nums, r+1, end, k)
        
    def partition(self, a, l, r, target):
        """
        3 ways partitions: to partition array into 3 groups:
            the group on the left side of l is smaller than target
            the group on the right side of r is greater than target.
        
        step1:inialized 3 pointers:
            l
            m=l
            r=len(a)-1
        step2: keep moving forward m until m <=r
            if middle value is less than target, swap m with l, then moving l and m forward
            if middle value is less than target, swap m with r, then moving r back
            if middle value is equal to target, just moving m forward(don't do anything)
        return two pointers l and r

        arr = [...target target target...]
                    l       k       r
          k 
                                k
        """
        m = l
        while m <= r:
            if a[m] < target:
                a[m], a[l] = a[l], a[m]
                l+=1
                m+=1
            elif a[m] > target:
                a[m], a[r] = a[r], a[m]
                r-=1
            else:
                m+=1
        return l, r