🧩 Problem Statement
Given an integer array nums and an integer k, return the kth largest element in the array.
Note: It’s the kth largest, not the kth distinct.
📘 Example
go
Input: nums = [3,2,1,5,6,4], k = 2
Output: 5
Input: nums = [3,2,3,1,2,4,5,5,6], k = 4
Output: 4
🧠 Approaches
You can solve this problem using either:
✅ Min Heap Approach (Optimal for large arrays)
Maintain a min-heap of size k. Push all elements into the heap, and remove the smallest whenever size exceeds k.
✅ Quickselect (Faster Average Case)
This is based on the quicksort idea and works in average O(n) time.
✅ Go Implementation (Min Heap)
go
package main
import (
"container/heap"
"fmt"
)
type MinHeap []int
func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(int)) }
func (h *MinHeap) Pop() interface{} {
old := *h
n := len(old)
val := old[n-1]
*h = old[0 : n-1]
return val
}
func findKthLargest(nums []int, k int) int {
h := &MinHeap{}
heap.Init(h)
for _, num := range nums {
heap.Push(h, num)
if h.Len() > k {
heap.Pop(h)
}
}
return (*h)[0]
}
📦 Example Usage
go
func main() {
fmt.Println(findKthLargest([]int{3, 2, 1, 5, 6, 4}, 2)) // Output: 5
fmt.Println(findKthLargest([]int{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4)) // Output: 4
}
⏱️ Time & Space Complexity
- Time: O(n log k)
- Space: O(k)
💡 Alternate: Quickselect (More efficient in practice)