Problem statement

Given an integer array nums and an integer k, return the k-th largest element (in sorted order, not the k-th distinct element).

Can you solve it without fully sorting the array?

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 <= 30
• -100 <= nums[i] <= 100

Hints for Kth Largest Element in an Array

1. Hint 1

   A min-heap of size k keeps exactly the k largest seen so far.

2. Hint 2

   Quickselect gives O(n) average time without a heap.

How to solve Kth Largest Element in an Array

You do not need the whole array in order — only the element that would land in one particular slot. Two ways to get it without a full sort: keep a min-heap of size k, which by construction always holds the k largest values seen so far with the k-th largest sitting on top; or run quickselect, which partitions around a pivot and recurses into only the side that contains the answer.

Approach

1. Heap approach: push each value into a min-heap; whenever the heap grows past k, pop the smallest.
2. After the scan the heap holds exactly the k largest values, and its root is the k-th largest.
3. Quickselect approach: partition around a pivot, then recurse only into the half that contains index n - k.
4. At these input sizes (n <= 30) simply sorting and indexing n - k is also entirely reasonable, which is what most of the reference solutions below do.

Why it works

The min-heap holds a running set of "best k so far". Popping the smallest whenever the size exceeds k can never discard a value that belongs in the final top k, because anything discarded is smaller than k other values already seen. So the invariant survives to the end, and the root — the minimum of the top k — is precisely the k-th largest.

Complexity

• Time — O(n log k) with a heap, O(n) average with quickselect
• Space — O(k)

Pitfalls

• This is the k-th largest by position in sorted order, not the k-th distinct value — duplicates each occupy a slot.
• After sorting ascending the answer is at index n - k, not k or k - 1. Off-by-one here is the classic mistake.
• Use a min-heap for the k largest. A max-heap of size k keeps the wrong end.

Reference solution

Python

from typing import List
import heapq

def findKthLargest(nums: List[int], k: int) -> int:
    heap = []
    for x in nums:
        heapq.heappush(heap, x)
        if len(heap) > k:
            heapq.heappop(heap)
    return heap[0]

Java

public static int findKthLargest(int[] nums, int k) {
    int[] s = nums.clone();
    Arrays.sort(s);
    return s[s.length - k];
}

C++

int findKthLargest(vector<int>& nums, int k) {
    vector<int> s = nums;
    sort(s.begin(), s.end());
    return s[(int) s.size() - k];
}

JavaScript

var findKthLargest = function(nums, k) {
    return nums.slice().sort(function(a, b) { return b - a; })[k - 1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium