Limited Time Offer:Up to 25% off Hello Interview Premium

⌘K

Tutor

Get Premium

Leetcode 215. Kth Largest Element in an Array

Return the k-th largest element (by sorted order, not distinct) from an unsorted array. For inputs up to ~1e5 elements, solve it faster than full sorting using selection techniques (e.g., Quickselect) or a size-k min-heap.

Asked at:

DESCRIPTION

Input:

nums = [3, 2, 1, 5, 6, 4], k = 2

Output:

Explanation: The 2nd largest element in the array is 5. When sorted: [1,2,3,4,5,6], the 2nd from the end is 5

Constraints:

1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
k is guaranteed to be valid (1 <= k <= array length)
Array elements may contain duplicates

Understanding the Problem

Let's understand what we're being asked to do. We have an unsorted array like [3, 2, 1, 5, 6, 4] and need to find the k-th largest element. For k=2, we want the 2nd largest element.

If we sorted the array: [1, 2, 3, 4, 5, 6], the 2nd largest would be 5 (at index length-2 from the end). But the problem says we should solve it faster than full sorting for large inputs.

Important constraint: We're looking for the k-th largest by sorted order, not distinct values. So if the array is [3, 2, 3, 1, 2, 4, 5, 5, 6] and k=4, the answer is 4 (the 4th element from the end when sorted: [1,2,2,3,3,4,5,5,6]).

Edge cases to consider: What if k=1 (largest element)? What if k equals the array length (smallest element)? What if the array has duplicates?

Brute Force Approach

The most straightforward approach is to sort the entire array in descending order, then return the element at index k-1. This guarantees we find the k-th largest element but requires sorting all elements even though we only need one value. For small arrays this is simple and effective, but for large inputs (~10^5 elements) we can do better by avoiding the full sort.

Visualization

def find_kth_largest(nums, k):
    """
    Brute force: Sort entire array in descending order,
    then return element at index k-1.
    Time: O(n log n), Space: O(1) or O(n) depending on sort.
    """
    # Sort the entire array in descending order
    nums.sort(reverse=True)
    
    # Return the k-th largest element (index k-1)
    return nums[k - 1]

Start finding k-th largest element

0 / 3

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log n) Sorting the array takes O(n log n) time using efficient algorithms like quicksort or mergesort

Space Complexity: O(1) or O(n) O(1) if sorting in-place, O(n) if the sorting algorithm requires additional space for merging or recursion

Building Intuition

We don't actually need the entire array sorted - we only care about finding the k-th largest element's position.

If we pick a pivot element and partition the array around it (smaller elements on left, larger on right), we know the pivot's final sorted position. If that position is exactly where the k-th largest should be, we're done!

By partitioning around a pivot, we can eliminate half the array from consideration. If the k-th largest is in the right partition, we don't need to look at the left partition at all.

This transforms an O(n log n) sorting problem into an average O(n) selection problem - we're doing less work because we're asking a simpler question.

Think about finding the tallest person in a room. You don't need to line everyone up by height (sorting). Instead, you could:

Pick someone at random as a reference
Split the room: taller people on the right, shorter on the left
Count how many are on the right - if it's exactly k-1, your reference person is the k-th tallest!
If more than k-1 are taller, repeat the process on the right side only
If fewer than k-1 are taller, repeat on the left side

This divide and conquer approach eliminates large portions of the search space with each step.

Common Mistakes

Using a max-heap instead of min-heap: a max-heap would track the k smallest elements, not the k largest

Forgetting to limit heap size to k: if the heap grows beyond k elements, the result will be incorrect

Confusing k-th largest with k-th distinct largest: the problem counts duplicates separately in sorted order

Not handling edge cases: k=1 (largest element) or k=n (smallest element) should work correctly

Assuming quickselect is always better: while it has O(n) average time, the heap approach has more predictable performance and is simpler to implement correctly

Optimal Solution

The optimal approach uses a min-heap of size k to track the k largest elements seen so far. Iterate through the array: for each element, if the heap has fewer than k elements, add it; otherwise, if the element is larger than the heap's minimum (top), remove the minimum and add the new element. After processing all elements, the heap's minimum is the k-th largest element. This approach is faster than full sorting because we only maintain k elements in the heap, and heap operations are logarithmic in k, not n.

Visualization

import heapq
def find_kth_largest(nums, k):
    """
    Find k-th largest element using min-heap of size k.
    Time: O(n log k), Space: O(k)
    """
    # Initialize min-heap to track k largest elements
    min_heap = []
    
    # Process each element in array
    for num in nums:
        # If heap has fewer than k elements, add current element
        if len(min_heap) < k:
            heapq.heappush(min_heap, num)
        # If current element is larger than heap minimum, replace it
        elif num > min_heap[0]:
            heapq.heapreplace(min_heap, num)
    
    # The root of min-heap is the k-th largest element
    return min_heap[0]

Start finding k-th largest element using min-heap

0 / 20

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n log k) We iterate through n elements, and for each element we may perform a heap operation (insert or remove) which takes O(log k) time. Total: O(n log k)

Space Complexity: O(k) The heap stores at most k elements at any time, requiring O(k) space

What We've Learned

Min-heap for top-K problems: When finding the k-th largest element, maintain a min-heap of size k - the root is always the k-th largest because smaller elements get evicted. This inverts intuition (min-heap for largest) but ensures O(n log k) efficiency by keeping the heap bounded.
Heap size maintenance pattern: The critical technique is adding elements then popping when size exceeds k - this ensures the heap contains exactly the k largest elements seen so far. Always check `heap.size() > k` after insertion, not before, to handle the initial k elements correctly.
Quickselect vs Heap tradeoff: Quickselect offers O(n) average time but O(n²) worst case and requires array modification, while heap guarantees O(n log k) with no modification and works on streams. Choose heap when k is small relative to n (k << n) or when data arrives incrementally.
K-th largest vs smallest confusion: A common mistake is using max-heap for k-th largest - remember that min-heap tracks largest elements (small values get removed) and max-heap tracks smallest elements (large values get removed). The heap type is opposite to what you're finding.
Space-time optimization insight: The heap approach uses O(k) space instead of O(n), making it superior when k is much smaller than n. For k = n/2 or larger, full sorting at O(n log n) may be more practical than O(n log k) since log k approaches log n.
Streaming data pattern: This heap technique extends to real-time top-K monitoring (trending items, leaderboards, anomaly detection) where you can't store all data. Each new element is processed in O(log k) time, making it perfect for continuous data streams or memory-constrained environments.

Test Your Understanding

Why is heap the right data structure for this problem?

heap provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Mid December, 2025

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 215. Kth Largest Element in an Array

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact