215. Kth Largest Element in an Array

Description

The task is to find the k-th largest element in an unsorted array. Given an array of integers, the goal is to identify the element that would be in the k-th position if the array were sorted in descending order.

Intuition

To solve this problem, we can use a frequency-based approach. By finding the largest element and determining the frequency of differences between this largest element and other elements, we can determine the k-th largest element efficiently.

Approach

1. Find the Largest Element: - Traverse the array to determine the maximum value (largest).
2. Calculate Frequencies: - Compute the frequency of each difference between largest and the elements in the array using a dictionary (freq).
3. Find the k-th Largest Element: - Iterate through the frequency dictionary to accumulate counts until reaching the k-th largest element.
4. Return the Result: - Compute the k-th largest element using the difference between the largest element and the count derived from the frequency dictionary.

Complexity

Time Complexity:

(O(n)), where (n) is the number of elements in the array. This is because we need to traverse the array twice: once to find the largest element and once to compute the frequency dictionary.

Space Complexity:

(O(n)), due to the space required for storing the frequency dictionary.

Code

C++

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        // find the largest element
        int largest = INT_MIN;
        
        for(int i = 0; i < nums.size(); ++i) {
            if(nums[i] > largest) largest = nums[i];
        }
        
        unordered_map hash;
        
        for(int i = 0; i < nums.size(); ++i) {
            int diff = largest - nums[i];
            hash[diff]++;
        }
        
        int count = 0;
        int diff = 0;
        while(count < k) {
            count += hash[diff];
            diff++;
        }
        
        return largest - diff + 1;
    }
};

Python

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        # Find the largest element
        largest = float('-inf')
        for num in nums:
            if num > largest:
                largest = num
        freq = {}
        for num in nums:
            diff = largest - num
            if diff in freq:
                freq[diff] += 1
            else:
                freq[diff] = 1
        count = 0
        diff = 0
        while count < k:
            count += freq.get(diff, 0)
            diff += 1

        return largest - diff + 1

Java

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // Find the largest element
        int largest = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num > largest) {
                largest = num;
            }
        }
        // Use a HashMap to store the frequency of differences
        Map hash = new HashMap<>();
        for (int num : nums) {
            int diff = largest - num;
            hash.put(diff, hash.getOrDefault(diff, 0) + 1);
        }

        // Determine the k-th largest element
        int count = 0;
        int diff = 0;
        while (count < k) {
            count += hash.getOrDefault(diff, 0);
            diff++;
        }

        return largest - diff + 1;
    }
}

JavaScript

var findKthLargest = function(nums, k) {
    // find the largest element
    let largest = -Infinity;
    
    for(let i=0;i largest) largest = nums[i];
    }
    const hash = {};
    
    for(let i=0;i