🎨Now live: Try our Free AI Image Generation Feature

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
- Find the Largest Element:
- Traverse the array to determine the maximum value (
largest
). - Calculate Frequencies:
- Compute the frequency of each difference between
largest
and the elements in the array using a dictionary (freq
). - Find the k-th Largest Element: - Iterate through the frequency dictionary to accumulate counts until reaching the k-th largest element.
- 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