Problem Statement:
Given an integer array nums and an integer kth, return the kth largest element in the array.
Note that it is the kth largest element in the sorted order, not the kth distinct element.
Can you solve it without sorting?
Example 1:
Input:
nums = [3,2,1,5,6,4], k = 2
Output:5
Example 2:
Input:
nums = [3,2,3,1,2,4,5,5,6], k = 4
Output:4
Constraints:
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
Approach:
- Use a min-heap to store the largest
kelements. - Traverse each number in
numsand push it into the heap. - If the heap size exceeds
k, remove the smallest element (heap root). - After processing all elements, the heap’s top (smallest in the heap) will be the k-th largest in the array.
Time Complexity:
Time Complexity = O(n log k)
Space Complexity:
Space Complexity = O(K)
Input: nums = [3, 2, 1, 5, 6, 4] k = 2
State Transitions:
Initialize: pq = MinPriorityQueue() i = 0 → nums[0] = 3 → pq.enqueue(3) → pq = [3] i = 1 → nums[1] = 2 → pq.enqueue(2) → pq = [2, 3] (min-heap: 2 is root) i = 2 → nums[2] = 1 → pq.enqueue(1) → pq = [1, 3, 2] → pq.size() = 3 > k (2) → pq.dequeue() removes smallest (1) → pq = [2, 3] i = 3 → nums[3] = 5 → pq.enqueue(5) → pq = [2, 3, 5] → pq.size() = 3 > k → pq.dequeue() removes smallest (2) → pq = [3, 5] i = 4 → nums[4] = 6 → pq.enqueue(6) → pq = [3, 5, 6] → pq.size() = 3 > k → pq.dequeue() removes smallest (3) → pq = [5, 6] i = 5 → nums[5] = 4 → pq.enqueue(4) → pq = [4, 6, 5] → pq.size() = 3 > k → pq.dequeue() removes smallest (4) → pq = [5, 6]Final Output:
5Explanation: pq.front() returns the smallest in the heap → the 2nd largest element overall.
var findKthLargest = function(nums, k) {
let pq = new MinPriorityQueue();
for(let i=0; i k) {
pq.dequeue();
}
}
return pq.front();
};
import heapq
def findKthLargest(nums, k):
pq = []
for num in nums:
heapq.heappush(pq, num)
if len(pq) > k:
heapq.heappop(pq)
return pq[0]
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKthLargest(nums, k))
import java.util.*;
public class Main {
public static int findKthLargest(int[] nums, int k) {
PriorityQueue pq = new PriorityQueue<>();
for (int num : nums) {
pq.add(num);
if (pq.size() > k) {
pq.poll();
}
}
return pq.peek();
}
public static void main(String[] args) {
int[] nums = {3, 2, 1, 5, 6, 4};
int k = 2;
System.out.println(findKthLargest(nums, k));
}
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
int findKthLargest(vector& nums, int k) {
priority_queue, greater> pq;
for (int num : nums) {
pq.push(num);
if (pq.size() > k) {
pq.pop();
}
}
return pq.top();
}
int main() {
vector nums = {3, 2, 1, 5, 6, 4};
int k = 2;
cout << findKthLargest(nums, k) << endl;
}
#include <stdio.h>
void heapify(int heap[], int n, int i) {
int smallest = i;
int left = 2*i + 1;
int right = 2*i + 2;
if (left < n && heap[left] < heap[smallest]) smallest = left;
if (right < n && heap[right] < heap[smallest]) smallest = right;
if (smallest != i) {
int temp = heap[i];
heap[i] = heap[smallest];
heap[smallest] = temp;
heapify(heap, n, smallest);
}
}
void pushHeap(int heap[], int *size, int val) {
heap[(*size)++] = val;
for (int i = (*size)/2 - 1; i >= 0; i--) {
heapify(heap, *size, i);
}
}
void popHeap(int heap[], int *size) {
heap[0] = heap[--(*size)];
for (int i = (*size)/2 - 1; i >= 0; i--) {
heapify(heap, *size, i);
}
}
int findKthLargest(int nums[], int n, int k) {
int heap[100];
int size = 0;
for (int i = 0; i < n; i++) {
pushHeap(heap, &size, nums[i]);
if (size > k) {
popHeap(heap, &size);
}
}
return heap[0];
}
int main() {
int nums[] = {3, 2, 1, 5, 6, 4};
int k = 2;
int n = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findKthLargest(nums, n, k));
}
using System;
using System.Collections.Generic;
class Program {
static int FindKthLargest(int[] nums, int k) {
var pq = new PriorityQueue();
foreach (var num in nums) {
pq.Enqueue(num, num);
if (pq.Count > k) {
pq.Dequeue();
}
}
return pq.Peek();
}
static void Main() {
int[] nums = { 3, 2, 1, 5, 6, 4 };
int k = 2;
Console.WriteLine(FindKthLargest(nums, k));
}
}
