215. Kth Largest Element In An Array - Explanation

Description

Given an unsorted array of integers nums and an integer k, return the kth largest element in the array.

By kth largest element, we mean the kth largest element in the sorted order, not the kth distinct element.

Follow-up: Can you solve it without sorting?

Example 1:

Input: nums = [2,3,1,5,4], k = 2

Output: 4

Example 2:

Input: nums = [2,3,1,1,5,5,4], k = 3

Output: 4

Constraints:

1 <= k <= nums.length <= 10000
-1000 <= nums[i] <= 1000

Topics

Recommended Time & Space Complexity

You should aim for a solution as good or better than O(nlogk) time and O(k) space, where n is the size of the input array, and k represents the rank of the largest number to be returned (i.e., the k-th largest element).

Hint 1

A naive solution would be to sort the array in descending order and return the k-th largest element. This would be an O(nlogn) solution. Can you think of a better way? Maybe you should think of a data structure which can maintain only the top k largest elements.

Hint 2

We can use a Min-Heap, which stores elements and keeps the smallest element at its top. When we add an element to the Min-Heap, it takes O(logk) time since we are storing k elements in it. Retrieving the top element (the smallest in the heap) takes O(1) time. How can this be useful for finding the k-th largest element?

Hint 3

The k-th largest element is the smallest element among the top k largest elements. This means we only need to maintain k elements in our Min-Heap to efficiently determine the k-th largest element. Whenever the size of the Min-Heap exceeds k, we remove the smallest element by popping from the heap. How do you implement this?

Hint 4

We initialize an empty Min-Heap. We iterate through the array and add elements to the heap. When the size of the heap exceeds k, we pop from the heap and continue. After the iteration, the top element of the heap is the k-th largest element.

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting Algorithms - Understanding how sorting works and its O(n log n) time complexity
Heap Data Structure - Using min-heaps to efficiently track the k largest elements
QuickSelect Algorithm - Partitioning arrays around a pivot to find the k-th element in average O(n) time
Two Pointers / Partitioning - Rearranging elements based on comparison with a pivot value

1. Sorting

Intuition

If you sort the entire array, all elements will be arranged from smallest to largest.
Once sorted:

The largest element is at the last position.
The 2nd largest is one position before that.
The k-th largest is simply at index n - k.

So the problem becomes:
→ Sort the array and pick the element that is k steps from the end.

This is simple but not the most efficient, because sorting takes O(n log n).

Algorithm

Sort the array in non-decreasing order.
Compute the index of the k-th largest element: index = n - k.
Return the element at that position.

class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums.sort()
        return nums[len(nums) - k]

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    findKthLargest(nums, k) {
        nums.sort((a, b) => a - b);
        return nums[nums.length - k];
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

2. Min-Heap

Intuition

Instead of sorting the whole array, we only need to keep track of the k largest elements seen so far.

A min-heap is perfect for this:

A min-heap always keeps the smallest element at the top.
If we maintain a heap of size k, then:
- the heap will always contain the k largest elements seen so far.
- the root of the heap (the smallest among these k) will be the k-th largest element.

Process:

Add elements into the heap.
If the heap grows larger than k, remove the smallest element.
At the end, the root of the heap is exactly the k-th largest element.

This avoids sorting the entire array and keeps memory small.

Algorithm

Create an empty min-heap.
Iterate through each number:
- Push the number into the min-heap.
- If the heap size exceeds k, pop the smallest element.
After processing all numbers, the top of the heap is the k-th largest element.
Return that value.

class Solution:
    def findKthLargest(self, nums, k):
        return heapq.nlargest(k, nums)[-1]

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        for (int num : nums) {
            minHeap.offer(num);
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }
        return minHeap.peek();
    }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minHeap;
        for (int num : nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        return minHeap.top();
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    findKthLargest(nums, k) {
        const minHeap = new MinPriorityQueue();
        for (let num of nums) {
            minHeap.push(num);
            if (minHeap.size() > k) {
                minHeap.pop();
            }
        }
        return minHeap.front();
    }
}

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        PriorityQueue<int, int> minHeap = new PriorityQueue<int, int>();
        foreach (int num in nums) {
            minHeap.Enqueue(num, num);
            if (minHeap.Count > k) {
                minHeap.Dequeue();
            }
        }
        return minHeap.Peek();
    }
}

func findKthLargest(nums []int, k int) int {
    minHeap := priorityqueue.NewWith(utils.IntComparator)

    for _, num := range nums {
        minHeap.Enqueue(num)
        if minHeap.Size() > k {
            minHeap.Dequeue()
        }
    }

    val, _ := minHeap.Peek()
    return val.(int)
}

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        val minHeap = PriorityQueue<Int>()

        for (num in nums) {
            minHeap.offer(num)
            if (minHeap.size > k) {
                minHeap.poll()
            }
        }
        return minHeap.peek()
    }
}

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var minHeap = Heap<Int>()

        for num in nums {
            minHeap.insert(num)
            if minHeap.count > k {
                _ = minHeap.removeMin()
            }
        }

        return minHeap.popMin()!
    }
}

Time & Space Complexity

Time complexity: $O(n \log k)$
Space complexity: $O(k)$

Where $n$ is the length of the array $nums$ .

3. Quick Select

Intuition

Quick Select is a selection algorithm that works like QuickSort but only explores the side of the array that contains the answer.

Key idea:

Pick a pivot.
Rearrange elements so that:
- all numbers smaller than or equal to the pivot go to the left,
- all numbers greater go to the right.
After partitioning, the pivot ends up in its correct sorted position.
Instead of sorting the whole array, we check:
- If the pivot’s final position is the index we want → answer found.
- Otherwise, recurse only into the side where the target index lies.

Because we eliminate half the array each time, this approach is much faster on average than full sorting.

For the k-th largest:

Convert it to the corresponding index in sorted order:
- index = n − k
Then use Quick Select to find the value that would appear at that index.

Algorithm

Convert k-th largest to its zero-based sorted index: target = n - k.
Use Quick Select between indices l and r:
- Choose a pivot (commonly the rightmost element).
- Partition the array around the pivot.
- Let the pivot's final index be p.
If p == target, return the pivot value.
If p > target, repeat Quick Select on the left half.
If p < target, repeat on the right half.
Continue until the target index is found.

class Solution:

    def findKthLargest(self, nums: List[int], k: int) -> int:
        k = len(nums) - k

        def quickSelect(l, r):
            pivot, p = nums[r], l
            for i in range(l, r):
                if nums[i] <= pivot:
                    nums[p], nums[i] = nums[i], nums[p]
                    p += 1
            nums[p], nums[r] = nums[r], nums[p]

            if p > k:
                return quickSelect(l, p - 1)
            elif p < k:
                return quickSelect(p + 1, r)
            else:
                return nums[p]

        return quickSelect(0, len(nums) - 1)

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        k = nums.length - k;

        return quickSelect(nums, 0, nums.length - 1, k);
    }

    private int quickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int p = left;

        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                int temp = nums[p];
                nums[p] = nums[i];
                nums[i] = temp;
                p++;
            }
        }

        int temp = nums[p];
        nums[p] = nums[right];
        nums[right] = temp;

        if (p > k) {
            return quickSelect(nums, left, p - 1, k);
        } else if (p < k) {
            return quickSelect(nums, p + 1, right, k);
        } else {
            return nums[p];
        }
    }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        k = nums.size() - k;
        return quickSelect(nums, 0, nums.size() - 1, k);
    }

    int quickSelect(vector<int>& nums, int left, int right, int k) {
        int pivot = nums[right];
        int p = left;

        for (int i = left; i < right; ++i) {
            if (nums[i] <= pivot) {
                swap(nums[p], nums[i]);
                p++;
            }
        }
        swap(nums[p], nums[right]);

        if (p > k) {
            return quickSelect(nums, left, p - 1, k);
        } else if (p < k) {
            return quickSelect(nums, p + 1, right, k);
        } else {
            return nums[p];
        }
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    findKthLargest(nums, k) {
        k = nums.length - k;

        const quickSelect = (left, right) => {
            let pivot = nums[right];
            let p = left;

            for (let i = left; i < right; i++) {
                if (nums[i] <= pivot) {
                    [nums[p], nums[i]] = [nums[i], nums[p]];
                    p++;
                }
            }
            [nums[p], nums[right]] = [nums[right], nums[p]];

            if (p > k) {
                return quickSelect(left, p - 1);
            } else if (p < k) {
                return quickSelect(p + 1, right);
            } else {
                return nums[p];
            }
        };

        return quickSelect(0, nums.length - 1);
    }
}

public class Solution {
    public int FindKthLargest(int[] nums, int k) {
        k = nums.Length - k;
        return QuickSelect(nums, 0, nums.Length - 1, k);
    }

    private int QuickSelect(int[] nums, int left, int right, int k) {
        int pivot = nums[right];
        int p = left;

        for (int i = left; i < right; i++) {
            if (nums[i] <= pivot) {
                int temp = nums[p];
                nums[p] = nums[i];
                nums[i] = temp;
                p++;
            }
        }

        int tmp = nums[p];
        nums[p] = nums[right];
        nums[right] = tmp;

        if (p > k) {
            return QuickSelect(nums, left, p - 1, k);
        } else if (p < k) {
            return QuickSelect(nums, p + 1, right, k);
        } else {
            return nums[p];
        }
    }
}

func findKthLargest(nums []int, k int) int {
    k = len(nums) - k

    var quickSelect func(l, r int) int
    quickSelect = func(l, r int) int {
        pivot, p := nums[r], l
        for i := l; i < r; i++ {
            if nums[i] <= pivot {
                nums[p], nums[i] = nums[i], nums[p]
                p++
            }
        }
        nums[p], nums[r] = nums[r], nums[p]

        if p > k {
            return quickSelect(l, p-1)
        } else if p < k {
            return quickSelect(p+1, r)
        } else {
            return nums[p]
        }
    }

    return quickSelect(0, len(nums)-1)
}

class Solution {
    fun findKthLargest(nums: IntArray, k: Int): Int {
        val target = nums.size - k

        fun quickSelect(l: Int, r: Int): Int {
            val pivot = nums[r]
            var p = l
            for (i in l until r) {
                if (nums[i] <= pivot) {
                    nums[p] = nums[i].also { nums[i] = nums[p] }
                    p++
                }
            }
            nums[p] = nums[r].also { nums[r] = nums[p] }

            return when {
                p > target -> quickSelect(l, p - 1)
                p < target -> quickSelect(p + 1, r)
                else -> nums[p]
            }
        }

        return quickSelect(0, nums.size - 1)
    }
}

class Solution {
    func findKthLargest(_ nums: [Int], _ k: Int) -> Int {
        var nums = nums
        let k = nums.count - k

        func quickSelect(_ l: Int, _ r: Int) -> Int {
            let pivot = nums[r]
            var p = l

            for i in l..<r {
                if nums[i] <= pivot {
                    nums.swapAt(i, p)
                    p += 1
                }
            }
            nums.swapAt(p, r)

            if p > k {
                return quickSelect(l, p - 1)
            } else if p < k {
                return quickSelect(p + 1, r)
            } else {
                return nums[p]
            }
        }

        return quickSelect(0, nums.count - 1)
    }
}

Time & Space Complexity

Time complexity: $O(n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(n)$

4. Quick Select (Optimal)

Intuition

Quick Select finds the k-th largest (or smallest) element without sorting the whole array.

This optimal version improves the classic Quick Select by:

choosing a pivot more intelligently (using a 3-element median-like technique),
reducing worst-case behavior,
partitioning the array efficiently so that large elements move left and small elements move right.

The key idea is still the same:

After partitioning, the pivot ends up exactly where it belongs in sorted order.
If the pivot’s final index is the one we need, we’re done.
Otherwise, we only search the half of the array where the answer lies.

This drastically reduces unnecessary work and leads to O(n) average time.

Algorithm

Convert k-th largest to zero-based index:
- targetIndex = k - 1 (because array is arranged in descending order in this variant).
Maintain two pointers: left = 0 and right = n - 1.
While searching:
- Choose a pivot using a more stable technique (swapping elements from left, left+1, right, mid).
- Partition the array so:
  - All elements > pivot move to the left.
  - All elements < pivot move to the right.
- The pivot ends at index j.
Compare:
- If j == targetIndex: return the pivot value.
- If j > targetIndex: search only in the left part (right = j - 1).
- If j < targetIndex: search only in the right part (left = j + 1).
Continue until the correct index is isolated.

class Solution:
    def partition(self, nums: List[int], left: int, right: int) -> int:
        mid = (left + right) >> 1
        nums[mid], nums[left + 1] = nums[left + 1], nums[mid]

        if nums[left] < nums[right]:
            nums[left], nums[right] = nums[right], nums[left]
        if nums[left + 1] < nums[right]:
            nums[left + 1], nums[right] = nums[right], nums[left + 1]
        if nums[left] < nums[left + 1]:
            nums[left], nums[left + 1] = nums[left + 1], nums[left]

        pivot = nums[left + 1]
        i = left + 1
        j = right

        while True:
            while True:
                i += 1
                if not nums[i] > pivot:
                    break
            while True:
                j -= 1
                if not nums[j] < pivot:
                    break
            if i > j:
                break
            nums[i], nums[j] = nums[j], nums[i]

        nums[left + 1], nums[j] = nums[j], nums[left + 1]
        return j

    def quickSelect(self, nums: List[int], k: int) -> int:
        left = 0
        right = len(nums) - 1

        while True:
            if right <= left + 1:
                if right == left + 1 and nums[right] > nums[left]:
                    nums[left], nums[right] = nums[right], nums[left]
                return nums[k]

            j = self.partition(nums, left, right)

            if j >= k:
                right = j - 1
            if j <= k:
                left = j + 1

    def findKthLargest(self, nums: List[int], k: int) -> int:
        return self.quickSelect(nums, k - 1)

public class Solution {
    private int partition(int[] nums, int left, int right) {
        int mid = (left + right) >> 1;
        swap(nums, mid, left + 1);

        if (nums[left] < nums[right])
            swap(nums, left, right);
        if (nums[left + 1] < nums[right])
            swap(nums, left + 1, right);
        if (nums[left] < nums[left + 1])
            swap(nums, left, left + 1);

        int pivot = nums[left + 1];
        int i = left + 1;
        int j = right;

        while (true) {
            while (nums[++i] > pivot);
            while (nums[--j] < pivot);
            if (i > j) break;
            swap(nums, i, j);
        }

        nums[left + 1] = nums[j];
        nums[j] = pivot;
        return j;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private int quickSelect(int[] nums, int k) {
        int left = 0;
        int right = nums.length - 1;

        while (true) {
            if (right <= left + 1) {
                if (right == left + 1 && nums[right] > nums[left])
                    swap(nums, left, right);
                return nums[k];
            }

            int j = partition(nums, left, right);

            if (j >= k) right = j - 1;
            if (j <= k) left = j + 1;
        }
    }

    public int findKthLargest(int[] nums, int k) {
        return quickSelect(nums, k - 1);
    }
}

class Solution {
public:
    int partition(vector<int>& nums, int left, int right) {
        int mid = (left + right) >> 1;
        swap(nums[mid], nums[left + 1]);

        if (nums[left] < nums[right])
            swap(nums[left], nums[right]);
        if (nums[left + 1] < nums[right])
            swap(nums[left + 1], nums[right]);
        if (nums[left] < nums[left + 1])
            swap(nums[left], nums[left + 1]);

        int pivot = nums[left + 1];
        int i = left + 1;
        int j = right;

        while (true) {
            while (nums[++i] > pivot);
            while (nums[--j] < pivot);
            if (i > j) break;
            swap(nums[i], nums[j]);
        }

        nums[left + 1] = nums[j];
        nums[j] = pivot;
        return j;
    }

    int quickSelect(vector<int>& nums, int k) {
        int left = 0;
        int right = nums.size() - 1;

        while (true) {
            if (right <= left + 1) {
                if (right == left + 1 && nums[right] > nums[left])
                    swap(nums[left], nums[right]);
                return nums[k];
            }

            int j = partition(nums, left, right);

            if (j >= k) right = j - 1;
            if (j <= k) left = j + 1;
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        return quickSelect(nums, k - 1);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @param {number} k
     * @return {number}
     */
    findKthLargest(nums, k) {
        function partition(left, right) {
            const mid = (left + right) >> 1;
            [nums[mid], nums[left + 1]] = [nums[left + 1], nums[mid]];

            if (nums[left] < nums[right])
                [nums[left], nums[right]] = [nums[right], nums[left]];
            if (nums[left + 1] < nums[right])
                [nums[left + 1], nums[right]] = [nums[right], nums[left + 1]];
            if (nums[left] < nums[left + 1])
                [nums[left], nums[left + 1]] = [nums[left + 1], nums[left]];

            const pivot = nums[left + 1];
            let i = left + 1;
            let j = right;

            while (true) {
                while (nums[++i] > pivot);
                while (nums[--j] < pivot);
                if (i > j) break;
                [nums[i], nums[j]] = [nums[j], nums[i]];
            }

            nums[left + 1] = nums[j];
            nums[j] = pivot;
            return j;
        }

        function quickSelect(k) {
            let left = 0;
            let right = nums.length - 1;

            while (true) {
                if (right <= left + 1) {
                    if (right == left + 1 && nums[right] > nums[left])
                        [nums[left], nums[right]] = [nums[right], nums[left]];
                    return nums[k];
                }

                const j = partition(left, right);

                if (j >= k) right = j - 1;
                if (j <= k) left = j + 1;
            }
        }

        return quickSelect(k - 1);
    }
}

public class Solution {
    private int Partition(int[] nums, int left, int right) {
        int mid = (left + right) >> 1;
        (nums[mid], nums[left + 1]) = (nums[left + 1], nums[mid]);

        if (nums[left] < nums[right])
            (nums[left], nums[right]) = (nums[right], nums[left]);
        if (nums[left + 1] < nums[right])
            (nums[left + 1], nums[right]) = (nums[right], nums[left + 1]);
        if (nums[left] < nums[left + 1])
            (nums[left], nums[left + 1]) = (nums[left + 1], nums[left]);

        int pivot = nums[left + 1];
        int i = left + 1;
        int j = right;

        while (true) {
            while (nums[++i] > pivot);
            while (nums[--j] < pivot);
            if (i > j) break;
            (nums[i], nums[j]) = (nums[j], nums[i]);
        }

        nums[left + 1] = nums[j];
        nums[j] = pivot;
        return j;
    }

    private int QuickSelect(int[] nums, int k) {
        int left = 0;
        int right = nums.Length - 1;

        while (true) {
            if (right <= left + 1) {
                if (right == left + 1 && nums[right] > nums[left])
                    (nums[left], nums[right]) = (nums[right], nums[left]);
                return nums[k];
            }

            int j = Partition(nums, left, right);

            if (j >= k) right = j - 1;
            if (j <= k) left = j + 1;
        }
    }

    public int FindKthLargest(int[] nums, int k) {
        return QuickSelect(nums, k - 1);
    }
}

func findKthLargest(nums []int, k int) int {
    var partition func(left, right int) int
    partition = func(left, right int) int {
        mid := (left + right) >> 1
        nums[mid], nums[left+1] = nums[left+1], nums[mid]

        if nums[left] < nums[right] {
            nums[left], nums[right] = nums[right], nums[left]
        }
        if nums[left+1] < nums[right] {
            nums[left+1], nums[right] = nums[right], nums[left+1]
        }
        if nums[left] < nums[left+1] {
            nums[left], nums[left+1] = nums[left+1], nums[left]
        }

        pivot := nums[left+1]
        i := left + 1
        j := right

        for {
            for i++; nums[i] > pivot; i++ {}
            for j--; nums[j] < pivot; j-- {}
            if i > j {
                break
            }
            nums[i], nums[j] = nums[j], nums[i]
        }

        nums[left+1], nums[j] = nums[j], nums[left+1]
        return j
    }

    quickSelect := func(k int) int {
        left := 0
        right := len(nums) - 1

        for {
            if right <= left+1 {
                if right == left+1 && nums[right] > nums[left] {
                    nums[left], nums[right] = nums[right], nums[left]
                }
                return nums[k]
            }

            j := partition(left, right)

            if j >= k {
                right = j - 1
            }
            if j <= k {
                left = j + 1
            }
        }
    }

    return quickSelect(k - 1)
}

class Solution {
    private fun partition(nums: IntArray, left: Int, right: Int): Int {
        val mid = (left + right) shr 1
        nums[mid] = nums[left + 1].also { nums[left + 1] = nums[mid] }

        if (nums[left] < nums[right])
            nums[left] = nums[right].also { nums[right] = nums[left] }
        if (nums[left + 1] < nums[right])
            nums[left + 1] = nums[right].also { nums[right] = nums[left + 1] }
        if (nums[left] < nums[left + 1])
            nums[left] = nums[left + 1].also { nums[left + 1] = nums[left] }

        val pivot = nums[left + 1]
        var i = left + 1
        var j = right

        while (true) {
            while (nums[++i] > pivot);
            while (nums[--j] < pivot);
            if (i > j) break
            nums[i] = nums[j].also { nums[j] = nums[i] }
        }

        nums[left + 1] = nums[j]
        nums[j] = pivot
        return j
    }

    private fun quickSelect(nums: IntArray, k: Int): Int {
        var left = 0
        var right = nums.size - 1

        while (true) {
            if (right <= left + 1) {
                if (right == left + 1 && nums[right] > nums[left])
                    nums[left] = nums[right].also { nums[right] = nums[left] }
                return nums[k]
            }

            val j = partition(nums, left, right)

            if (j >= k) right = j - 1
            if (j <= k) left = j + 1
        }
    }

    fun findKthLargest(nums: IntArray, k: Int): Int {
        return quickSelect(nums, k - 1)
    }
}

Time & Space Complexity

Time complexity: $O(n)$ in average case, $O(n ^ 2)$ in worst case.
Space complexity: $O(1)$

Common Pitfalls

Confusing K-th Largest With K-th Smallest

The problem asks for the k-th largest element, not the k-th smallest. When using sorting, the k-th largest is at index n - k, not at index k - 1. Similarly, in QuickSelect, you must convert to the correct target index. Mixing up these indices is a very common source of off-by-one errors.

Using a Max-Heap Instead of a Min-Heap

For the heap approach, a min-heap of size k is the correct choice because it keeps the smallest of the k largest elements at the top. Using a max-heap would require storing all n elements and extracting k times, which is less efficient. The min-heap approach maintains O(k) space and O(n log k) time.

QuickSelect Worst Case on Sorted Arrays

QuickSelect degrades to O(n^2) time when the pivot choice is consistently poor, such as always picking the last element on an already sorted or reverse-sorted array. This can cause time limit exceeded errors. Using randomized pivot selection or median-of-three pivot selection helps avoid this worst case and keeps the average complexity at O(n).