🎨 Try our Free AI Image Generation Feature

215. Kth Largest Element in an Array

avatar
Dare2Solve

11 months ago

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