Kth Largest Element in an Array solution and explanation
IBM
9 more videos on this problem
Kth Largest Element in an Array - Quick Select - Leetcode 215 - PythonNeetCode · 18:48 · 421K views
Kth Largest Element in an Array - Leetcode 215 - Heaps (Python)Greg Hogg · 11:52 · 34K views
Leetcode Kth Largest Element in an Array | Solving AlgoPrep 151 | Nishant ChaharAlgoPrep · 8:10 · 21K views
Kth Largest Element in an Array | Live Coding with Explanation | Leetcode - 215Algorithms Made Easy · 6:55 · 19K views
Kth Largest Element in an Array | Heap | Sorting | 2 Approaches | Time Complexity | Leetcode-215codestorywithMIK · 9:18 · 18K views
How to find the kth largest element in an array? (LeetCode .215) - Inside codeInside code · 7:01 · 11K views
Kth Largest Element In An Array - 215. LeetCode - QuickSelect - JavaTeddy Smith · 14:16 · 4K views
Kth Largest Element in an Array - LeetCode 215 - Python #leetcode #heap #quickselectDeepti Talesra · 23:20 · 3K views
215. Kth Largest Element in an Array - MinHeap - LeetCode Daily Challenge - JavaScriptLeetCodeWithMonu · 15:27 · 3K views
Kth Largest Element in an Array | LeetCode 215 (Medium)Destination FAANG · 8:18 · 2K views
The problem
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.
import heapq
def findKthLargest(nums, k):
minHeap = []
for num in nums:
heapq.heappush(minHeap, num)
if len(minHeap) > k:
heapq.heappop(minHeap)
return minHeap[0]
nums = [3,2,1,5,6,4]
k = 2
print(findKthLargest(nums, k))import java.util.PriorityQueue;
public class KthLargestElement {
public static int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int num : nums) {
minHeap.add(num);
if (minHeap.size() > k) {
minHeap.poll();
}
}
return minHeap.peek();
}
public static void main(String[] args) {
int[] nums = {3,2,1,5,6,4};
int k = 2;
System.out.println(findKthLargest(nums, k));
}
}#include <iostream>
#include <vector>
#include <queue>
int findKthLargest(std::vector<int>& nums, int k) {
std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
for (int num : nums) {
minHeap.push(num);
if (minHeap.size() > k) {
minHeap.pop();
}
}
return minHeap.top();
}
int main() {
std::vector<int> nums = {3,2,1,5,6,4};
int k = 2;
std::cout << findKthLargest(nums, k) << std::endl;
return 0;
}var findKthLargest = function(nums, k) {
const minHeap = [];
for (let num of nums) {
minHeap.push(num);
minHeap.sort((a, b) => a - b); // Keep sorting the heap
if (minHeap.length > k) {
minHeap.shift(); // Remove smallest element to maintain heap size
}
}
return minHeap[0];
};
let nums = [3,2,1,5,6,4];
let k = 2;
console.log(findKthLargest(nums, k));#include <stdio.h>
#include <stdlib.h>
int cmpfunc (const void * a, const void * b) {
return (*(int*)a - *(int*)b);
}
int findKthLargest(int* nums, int numsSize, int k) {
qsort(nums, numsSize, sizeof(int), cmpfunc);
return nums[numsSize - k];
}
int main() {
int nums[] = {3,2,1,5,6,4};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findKthLargest(nums, numsSize, k));
return 0;
}using System;
using System.Collections.Generic;
class KthLargestElement {
static int FindKthLargest(int[] nums, int k) {
SortedSet<(int, int)> minHeap = new SortedSet<(int, int)>();
foreach (int num in nums) {
minHeap.Add((num, num));
if (minHeap.Count > k) {
minHeap.Remove(minHeap.Min);
}
}
return minHeap.Min.Item1;
}
static void Main() {
int[] nums = {3,2,1,5,6,4};
int k = 2;
Console.WriteLine(FindKthLargest(nums, k));
}
}We use Python's heapq module to maintain a min-heap. For each element in the array, the element is pushed to the heap. If the heap size exceeds k, the smallest element is popped. The smallest element remaining in the heap is the kth largest element.
Time Complexity: O(n log k), where n is the number of elements in the input array.
Space Complexity: O(k), where k is the size of the min-heap.
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.
import random
def partition(nums, left, right, pivot_index):
pivot_value = nums[pivot_index]
nums[pivot_index], nums[right] = nums[right], nums[pivot_index] # move pivot to end
store_index = left
for i in range(left, right):
if nums[i] > pivot_value:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
nums[right], nums[store_index] = nums[store_index], nums[right] # move pivot to its final place
return store_index
def quickSelect(nums, left, right, k):
if left == right:
return nums[left]
pivot_index = random.randint(left, right)
pivot_index = partition(nums, left, right, pivot_index)
if k == pivot_index:
return nums[k]
elif k < pivot_index:
return quickSelect(nums, left, pivot_index - 1, k)
else:
return quickSelect(nums, pivot_index + 1, right, k)
def findKthLargest(nums, k):
return quickSelect(nums, 0, len(nums) - 1, k - 1)
nums = [3, 2, 1, 5, 6, 4]
k = 2
print(findKthLargest(nums, k))import java.util.Random;
public class KthLargestElement {
private static int partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
int newPivotIndex = left;
swap(nums, pivotIndex, right);
for (int i = left; i < right; i++) {
if (nums[i] > pivotValue) {
swap(nums, newPivotIndex++, i);
}
}
swap(nums, right, newPivotIndex);
return newPivotIndex;
}
private static void swap(int[] nums, int a, int b) {
int temp = nums[a];
nums[a] = nums[b];
nums[b] = temp;
}
private static int quickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
Random rand = new Random();
int pivotIndex = left + rand.nextInt(right - left + 1);
pivotIndex = partition(nums, left, right, pivotIndex);
if (pivotIndex == k) return nums[k];
else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
else return quickSelect(nums, left, pivotIndex - 1, k);
}
public static int findKthLargest(int[] nums, int k) {
int n = nums.length;
return quickSelect(nums, 0, n - 1, k - 1);
}
public static void main(String[] args) {
int[] nums = {3,2,1,5,6,4};
int k = 2;
System.out.println(findKthLargest(nums, k));
}
}#include <iostream>
#include <vector>
#include <algorithm>
int partition(std::vector<int>& nums, int left, int right) {
int pivot = nums[right];
int i = left;
for (int j = left; j < right; ++j) {
if (nums[j] > pivot) {
std::swap(nums[i++], nums[j]);
}
}
std::swap(nums[i], nums[right]);
return i;
}
int quickSelect(std::vector<int>& nums, int left, int right, int k) {
if (left < right) {
int pivotIndex = partition(nums, left, right);
if (pivotIndex == k) return nums[pivotIndex];
else if (pivotIndex < k) return quickSelect(nums, pivotIndex + 1, right, k);
else return quickSelect(nums, left, pivotIndex - 1, k);
}
return nums[left]; // if left == right
}
int findKthLargest(std::vector<int>& nums, int k) {
return quickSelect(nums, 0, nums.size() - 1, k - 1);
}
int main() {
std::vector<int> nums = {3,2,1,5,6,4};
int k = 2;
std::cout << findKthLargest(nums, k) << std::endl;
return 0;
}#include <stdio.h>
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
}
int partition(int *nums, int low, int high) {
int pivot = nums[high];
int i = low;
for (int j = low; j < high; j++) {
if (nums[j] > pivot) {
swap(&nums[i], &nums[j]);
i++;
}
}
swap(&nums[i], &nums[high]);
return i;
}
int quickSelect(int *nums, int low, int high, int k) {
if (low <= high) {
int pi = partition(nums, low, high);
if (pi == k) return nums[pi];
else if (pi < k) return quickSelect(nums, pi + 1, high, k);
else return quickSelect(nums, low, pi - 1, k);
}
return -1;
}
int findKthLargest(int* nums, int numsSize, int k) {
return quickSelect(nums, 0, numsSize - 1, k - 1);
}
int main() {
int nums[] = {3,2,1,5,6,4};
int k = 2;
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", findKthLargest(nums, numsSize, k));
return 0;
}using System;
class KthLargestElement {
private static int Partition(int[] nums, int left, int right, int pivotIndex) {
int pivotValue = nums[pivotIndex];
Swap(ref nums[pivotIndex], ref nums[right]);
int newPivotIndex = left;
for (int i = left; i < right; i++) {
if (nums[i] > pivotValue) {
Swap(ref nums[newPivotIndex++], ref nums[i]);
}
}
Swap(ref nums[newPivotIndex], ref nums[right]);
return newPivotIndex;
}
private static void Swap(ref int a, ref int b) {
int temp = a;
a = b;
b = temp;
}
private static int QuickSelect(int[] nums, int left, int right, int k) {
if (left == right) return nums[left];
Random rand = new Random();
int pivotIndex = rand.Next(left, right + 1);
pivotIndex = Partition(nums, left, right, pivotIndex);
if (pivotIndex == k) return nums[k];
else if (pivotIndex < k) return QuickSelect(nums, pivotIndex + 1, right, k);
else return QuickSelect(nums, left, pivotIndex - 1, k);
}
public static int FindKthLargest(int[] nums, int k) {
return QuickSelect(nums, 0, nums.Length - 1, k - 1);
}
static void Main() {
int[] nums = {3,2,1,5,6,4};
int k = 2;
Console.WriteLine(FindKthLargest(nums, k));
}
}The Python method takes advantage of Python's dynamic lists and absence of static partitioning constraints. A randomized pivot helps further eliminate edge case pitfalls akin to performance degradation prevalent in non-randomized variants of Quickselect.
Average-case Time Complexity: O(n), possible from random selection reducing chance of consistently poor splits.
Space Complexity: O(log n) inherent to recursion depth.
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.
function findKthLargest(nums: number[], k: number): number {
const n = nums.length;
k = n - k;
const quickSort = (l: number, r: number): number => {
if (l === r) {
return nums[l];
}
let [i, j] = [l - 1, r + 1];
const x = nums[(l + r) >> 1];
while (i < j) {
while (nums[++i] < x);
while (nums[--j] > x);
if (i < j) {
[nums[i], nums[j]] = [nums[j], nums[i]];
}
}
if (j < k) {
return quickSort(j + 1, r);
}
return quickSort(l, j);
};
return quickSort(0, n - 1);
}func findKthLargest(nums []int, k int) int {
k = len(nums) - k
var quickSort func(l, r int) int
quickSort = func(l, r int) int {
if l == r {
return nums[l]
}
i, j := l-1, r+1
x := nums[(l+r)>>1]
for i < j {
for {
i++
if nums[i] >= x {
break
}
}
for {
j--
if nums[j] <= x {
break
}
}
if i < j {
nums[i], nums[j] = nums[j], nums[i]
}
}
if j < k {
return quickSort(j+1, r)
}
return quickSort(l, j)
}
return quickSort(0, len(nums)-1)
}impl Solution {
pub fn find_kth_largest(mut nums: Vec<i32>, k: i32) -> i32 {
let len = nums.len();
let k = len - k as usize;
Self::quick_sort(&mut nums, 0, len - 1, k)
}
fn quick_sort(nums: &mut Vec<i32>, l: usize, r: usize, k: usize) -> i32 {
if l == r {
return nums[l];
}
let (mut i, mut j) = (l as isize - 1, r as isize + 1);
let x = nums[(l + r) / 2];
while i < j {
i += 1;
while nums[i as usize] < x {
i += 1;
}
j -= 1;
while nums[j as usize] > x {
j -= 1;
}
if i < j {
nums.swap(i as usize, j as usize);
}
}
let j = j as usize;
if j < k {
Self::quick_sort(nums, j + 1, r, k)
} else {
Self::quick_sort(nums, l, j, k)
}
}
}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.
function findKthLargest(nums: number[], k: number): number {
const minQ = new MinPriorityQueue<number>();
for (const x of nums) {
minQ.enqueue(x);
if (minQ.size() > k) {
minQ.dequeue();
}
}
return minQ.front();
}func findKthLargest(nums []int, k int) int {
minQ := hp{}
for _, x := range nums {
heap.Push(&minQ, x)
if minQ.Len() > k {
heap.Pop(&minQ)
}
}
return minQ.IntSlice[0]
}
type hp struct{ sort.IntSlice }
func (h hp) Less(i, j int) bool { return h.IntSlice[i] < h.IntSlice[j] }
func (h *hp) Push(v any) { h.IntSlice = append(h.IntSlice, v.(int)) }
func (h *hp) Pop() any {
a := h.IntSlice
v := a[len(a)-1]
h.IntSlice = a[:len(a)-1]
return v
}use std::collections::BinaryHeap;
impl Solution {
pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
let mut minQ = BinaryHeap::new();
for &x in nums.iter() {
minQ.push(-x);
if minQ.len() > k as usize {
minQ.pop();
}
}
-minQ.peek().unwrap()
}
}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.
function findKthLargest(nums: number[], k: number): number {
const cnt: Record<number, number> = {};
for (const x of nums) {
cnt[x] = (cnt[x] || 0) + 1;
}
const m = Math.max(...nums);
for (let i = m; ; --i) {
k -= cnt[i] || 0;
if (k <= 0) {
return i;
}
}
}func findKthLargest(nums []int, k int) int {
cnt := map[int]int{}
m := -(1 << 30)
for _, x := range nums {
cnt[x]++
m = max(m, x)
}
for i := m; ; i-- {
k -= cnt[i]
if k <= 0 {
return i
}
}
}use std::collections::HashMap;
impl Solution {
pub fn find_kth_largest(nums: Vec<i32>, k: i32) -> i32 {
let mut cnt = HashMap::new();
let mut m = i32::MIN;
for &x in &nums {
*cnt.entry(x).or_insert(0) += 1;
if x > m {
m = x;
}
}
let mut k = k;
for i in (i32::MIN..=m).rev() {
if let Some(&count) = cnt.get(&i) {
k -= count;
if k <= 0 {
return i;
}
}
}
unreachable!();
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Using a Min-Heap (Priority Queue) | Time Complexity: O(n log k), where n is the number of elements in the input array. |
| Quickselect Algorithm | Average-case Time Complexity: O(n), possible from random selection reducing chance of consistently poor splits. |
| Quick Select | – |
| Priority Queue (Min Heap) | – |
| Counting Sort | – |
Complexity analysis
| Approach | Time | Space | When 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. |
| Quickselect | Average O(n), Worst O(n²) | O(1) iterative or O(log n) recursion | Best for optimal average performance when modifying the array is allowed and full sorting is unnecessary. |
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.