Kth Largest Element In An Array

Sort ascending and read the element k from the end.

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

Correct and simple, but sorts the entire array to answer a question about a single position.

Keep a min-heap holding only the k largest values seen so far; its root is the smallest of those k, i.e. exactly the kth largest overall. Seed the heap with the first k numbers, then for every remaining number, only bother pushing it if it beats the current root — smaller numbers can never be in the top k and are skipped for free.

import heapq

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        heap = nums[:k]
        heapq.heapify(heap)
        for n in nums[k:]:
            if n > heap[0]:
                heapq.heapreplace(heap, n)  # pop root, push n
        return heap[0]

Tracing nums = [3, 2, 1, 5, 6, 4], k = 2 (heap array, root at index 0 is the current 2nd largest):

Correctness: the heap only ever retains the k largest values processed so far; any number smaller than the root is provably outside the top k no matter what comes later (more competition only raises the bar). Once every number is processed, the root is the smallest of the true top k, which is the kth largest.

Complexity: building the initial heap is O(k), and each of the remaining n-k numbers costs at most O(log k) for a conditional replace → O(n log k) overall. Space is O(k) for the heap.

Quicksort partitions around a pivot so everything smaller ends up on one side and everything larger on the other. Quickselect uses the same partition step, but only ever recurses into the one side that contains the target index — the other side is discarded entirely, which is what gets the average case down to linear instead of n log n.

The kth largest is the element that would land at index n - k in ascending sorted order, so that’s the target index we partition toward. A random pivot matters here — LeetCode includes adversarial test cases that make a fixed pivot (e.g. always picking the last element) degrade to O(n²).

import random

class Solution:
    def findKthLargest(self, nums: list[int], k: int) -> int:
        target = len(nums) - k

        def partition(left: int, right: int) -> int:
            pivot_index = random.randint(left, right)
            pivot = nums[pivot_index]
            nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
            store = left
            for i in range(left, right):
                if nums[i] < pivot:
                    nums[store], nums[i] = nums[i], nums[store]
                    store += 1
            nums[store], nums[right] = nums[right], nums[store]
            return store

        left, right = 0, len(nums) - 1
        while True:
            p = partition(left, right)
            if p == target:
                return nums[p]
            elif p < target:
                left = p + 1
            else:
                right = p - 1

Correctness: after each partition, the element at index p is in its final sorted position — everything left of p is <= it, everything right is >= it. If p is the target index we’re done; otherwise the target must lie strictly on one side, so it’s safe to discard the other side and recurse only into the half that matters.

Complexity: on average each partition roughly halves the search space, giving n + n/2 + n/4 + ... ≈ 2n work → O(n) average. With a bad pivot choice every partition could shrink the range by only one element, giving O(n²) worst case — random pivots make this exceedingly unlikely in practice. Partitioning is done in place, so space is O(1) (ignoring recursion — this iterative version uses none).