Skip to main content
Talentd

Kth Largest Element in an Array - Solution & Explanation

MediumArrayDivide and ConquerSortingHeap (Priority Queue)27 min readAsked at: Amazon, Microsoft, Apple +38
Practice this problem

Problem Statement

Given an integer array nums and an integer k, 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 Overview

Problem Overview: Given an unsorted integer array, return the kth largest element. The array is not sorted and duplicates may exist. The goal is to identify the element that would appear at position k if the array were sorted in descending order.

Approach 1: Min-Heap (Priority Queue) (Time: O(n log k), Space: O(k))

This approach keeps only the k largest elements seen so far using a min-heap. Iterate through the array and push each number into the heap. If the heap size exceeds k, remove the smallest element using pop(). The heap always contains the top k largest elements, and the root represents the kth largest overall. This method works well when k is much smaller than n and leverages efficient heap operations from a heap (priority queue). The approach is easy to implement and predictable in performance.

Approach 2: Quickselect Algorithm (Average Time: O(n), Worst Case: O(n²), Space: O(1) or O(log n) recursion)

Quickselect is a selection algorithm derived from QuickSort. Instead of fully sorting the array, it repeatedly partitions the array around a pivot. After partitioning, the pivot lands in its correct sorted position. Compare this index with the target index n - k. If they match, you found the kth largest element. Otherwise, recurse into the left or right partition depending on where the target lies. This approach uses the partition idea from divide and conquer and avoids unnecessary sorting work. Average performance is linear, making it one of the fastest practical solutions.

Recommended for interviews: Start by mentioning the heap approach since it is straightforward and guarantees O(n log k) time. Then present Quickselect as the optimal solution with average O(n) time. Interviewers typically expect you to recognize that a full sorting pass (O(n log n)) is unnecessary and that selection algorithms can locate the kth element faster.

Approach 1: Using a Min-Heap (Priority Queue)

By using a Min-Heap, we can efficiently keep track of the k largest elements. Maintain a heap of size k, and for each element in the array, decide whether to add it to the heap. If you add an element to the heap when it is full, remove the minimum element to maintain the size of the heap as k. At the end, the root of the heap will be the kth largest element.

We first define a comparison function cmpfunc that is used by the C library function qsort to sort the array. After sorting, the kth largest element is located at index numsSize - k.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.

Try this approach in the editor →

Approach 2: Quickselect Algorithm

Quickselect is an efficient selection algorithm to find the kth smallest element in an unordered list. The algorithm is related to the quicksort sorting algorithm. It works by partitioning the data, similar to the partitioning step of quicksort, and is based on the idea of reducing the problem size through partitioning.

The quickSelect function recursively partitions the array around pivot elements. The function partition ensures the pivot is in its sorted position with all larger numbers left and smaller numbers right. If the pivot's index equals k, the pivot is the kth largest element. We adjust to 0-based index during each call.

Code

CC++JavaPythonC#

C

C++

Java

Python

C#

Complexity

Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.

Try this approach in the editor →

Approach 3: Quick Select

Quick Select is an algorithm for finding the k^{th} largest or smallest element in an unsorted array. Its basic idea is to select a pivot element each time, dividing the array into two parts: one part contains elements smaller than the pivot, and the other part contains elements larger than the pivot. Then, based on the position of the pivot, it decides whether to continue the search on the left or right side until the k^{th} largest element is found.

The time complexity is O(n), and the space complexity is O(log n). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 4: Priority Queue (Min Heap)

We can maintain a min heap minQ of size k, and then iterate through the array nums, adding each element to the min heap. When the size of the min heap exceeds k, we pop the top element of the heap. This way, the final k elements in the min heap are the k largest elements in the array, and the top element of the heap is the k^{th} largest element.

The time complexity is O(nlog k), and the space complexity is O(k). Here, n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Approach 5: Counting Sort

We can use the idea of counting sort, counting the occurrence of each element in the array nums and recording it in a hash table cnt. Then, we iterate over the elements i from largest to smallest, subtracting the occurrence count cnt[i] each time, until k is less than or equal to 0. At this point, the element i is the k^{th} largest element in the array.

The time complexity is O(n + m), and the space complexity is O(n). Here, n is the length of the array nums, and m is the maximum value among the elements in nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Using a Min-Heap (Priority Queue)

Time Complexity: O(n log n), where n is the size of the array, because of the sorting operation.
Space Complexity: O(1), as we are modifying the input array in-place.

Quickselect Algorithm

Average-case Time Complexity: O(n), but worst-case O(n²).
Space Complexity: O(1) for iterative solution, O(log n) for recursive calls due to stack depth.

Quick Select—
Priority Queue (Min Heap)—
Counting Sort—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Min-Heap (Priority Queue)O(n log k)O(k)Best when k is small compared to n and you want predictable performance using heap operations.
QuickselectAverage O(n), Worst O(n²)O(1) iterative or O(log n) recursionBest for optimal average performance when modifying the array is allowed and full sorting is unnecessary.

Video Solution

Kth Largest Element in an Array - Quick Select - Leetcode 215 - Python • NeetCode • 421,129 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Kth Largest Element in an Array easy or hard?
Kth Largest Element in an Array is generally classified as a medium difficulty problem. The heap solution is straightforward, but recognizing that Quickselect can reduce the complexity to average O(n) requires deeper algorithm knowledge.
How to solve Kth Largest Element in an Array in O(n)?
Use the Quickselect algorithm. Partition the array around a pivot and check the pivot's final index. Compare it with the target index n - k, then recursively search only the relevant partition. Because each step discards roughly half of the remaining elements on average, the expected running time becomes O(n).
Kth Largest Element in an Array Python or Java solution?
Python solutions typically use the heapq library to maintain a min-heap of size k, giving O(n log k) time complexity. Java implementations often use PriorityQueue for the same approach. Quickselect can also be implemented in both languages using in-place partitioning for average O(n) performance.
What is the best approach for Kth Largest Element in an Array?
Quickselect is generally considered the best approach because it finds the kth element in average O(n) time without sorting the entire array. It partitions the array similar to QuickSort and recursively searches only the side containing the target index. A min-heap approach is also popular in interviews because it is simpler and guarantees O(n log k) time.
Is Kth Largest Element in an Array asked at Google/Amazon/Meta?
Kth Largest Element in an Array is a common interview question at companies like Amazon, Google, Meta, and Microsoft. It tests knowledge of heaps, partitioning, and selection algorithms such as Quickselect. Variants also appear in streaming and top-k problems.
What data structure is used in Kth Largest Element in an Array?
The most common data structure used is a min-heap (priority queue). The heap keeps track of the top k largest elements while scanning the array. Quickselect solutions rely more on array partitioning rather than additional data structures.
What is the time complexity of Kth Largest Element in an Array?
Time complexity depends on the approach used. A min-heap solution runs in O(n log k) time with O(k) space. The Quickselect algorithm runs in average O(n) time and O(1) extra space, though the worst case can degrade to O(n²) if pivot selection is poor.

Ready to solve this problem?

Practice Kth Largest Element in an Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Find Subsequence of Length K With the Largest Sum

Next

Find the Kth Largest Integer in the Array