Kth Largest Element in an Array

Medium

The problem

Return the k-th largest number in nums. This means the k-th number if the array were sorted from biggest to smallest, so duplicates count separately.

Example 1
Input: nums = [3, 2, 1, 5, 6, 4], k = 2
Output: 5
From biggest to smallest: 6, 5, 4, ... so the 2nd is 5.
Example 2
Input: nums = [3, 2, 3, 1, 2, 4, 5, 5, 6], k = 4
Output: 4
From biggest to smallest: 6, 5, 5, 4, ... so the 4th is 4.

Limits

1 ≤ k ≤ nums.length ≤ 100,000
-10,000 ≤ nums[i] ≤ 10,000

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Same idea as the stream problem, but all numbers are given at once.

The idea

Min-heap of size k (O(n log k)), or quickselect for O(n) average.

Target: O(n log k) time, O(k) space

Go function shape

func findKthLargest(nums []int, k int) int

Reference solution

Tested with go test. Try it yourself first, then compare.

// FindKthLargest: keep a min-heap of the k largest values seen so far.
// The root is the smallest of those k, which is exactly the kth largest overall.
func FindKthLargest(nums []int, k int) int {
	h := &IntHeap{}
	for _, v := range nums {
		heap.Push(h, v)
		if h.Len() > k {
			heap.Pop(h) // evict the smallest: it can no longer be in the top k
		}
	}
	return (*h)[0]
}

Read the lesson: Heap / Top-K