Dare2Solve
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.
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.
Find the Largest Element:
largest
).Calculate Frequencies:
largest
and the elements in the array using a dictionary (freq
).Find the k-th Largest Element:
Return the Result:
(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.
(O(n)), due to the space required for storing the frequency dictionary.
class Solution {
public:
int findKthLargest(vector<int>& 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<int, int> 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;
}
};
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
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<Integer, Integer> 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;
}
}
var findKthLargest = function(nums, k) {
// find the largest element
let largest = -Infinity;
for(let i=0;i<nums.length;i++){
if(nums[i] > largest) largest = nums[i];
}
const hash = {};
for(let i=0;i<nums.length;i++){
const diff = largest-nums[i];
hash[diff] = (hash[diff] || 0) + 1;
}
let count = 0;
let diff = 0;
while(count<k){
count += (hash[diff] || 0);
diff++;
}
return largest - diff + 1;
};