215.Kth_Largest_Element_in_an_Array_(Medium).md

215. Kth Largest Element in an Array (Medium)

Date and Time: Jun 25, 2024, 23:23 (EST)

Link: https://leetcode.com/problems/kth-largest-element-in-an-array/

Edge Case:

Input: nums = [-3,-2,-1,-5,-6,-4], k = 2
Output: -2

Walk-through:

Maintain a minHeap with only k elements, then return the top of the minHeap will be the kth largest element.

My Solution:

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Q: Return the kth largest element from nums
        # S: Maintain a minHeap to sort elements in order
        # When len(minHeap) < k, append elements into minHeap
        # If nums[i] >= minHeap[0], heappush new element, if len(minHeap) > 2, heappush()
        # Finally, return minHeap[0], this is the kth largest element
        # TC: O(nlogk), n=len(nums), SC: O(k)

        minHeap = []
        for n in nums:
            if len(minHeap) < k:
                heapq.heappush(minHeap, n)
            else:
                # Check if n > minHeap[0]
                if n > minHeap[0]:
                    if len(minHeap) == k:
                        heapq.heappop(minHeap)
                    heapq.heappush(minHeap, n)
        return minHeap[0]

Time Complexity: $O(nlog\ k)$, heapify takes $O(nlogn)$.
Space Complexity: $O(k)$, created extra space with k elements.

Java

class Solution {
    /* 
    Use PQ to sort elements
    TC: O(nlogk), n=nums.length, SC: O(k)
    */
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for (int n: nums) {
            // Check if PQ meets capacity
            if (pq.size() < k) {
                pq.add(n);
            } else {
                // If n > pq[0], add n
                if (n > pq.peek()) {
                    // Check the size to remove smaller element
                    if (pq.size() == k) {
                        pq.poll();
                    }
                    pq.add(n);
                }
            }
        }
        return pq.peek();
    }
}