Domain 2MediumCORE

Kth Largest Element in an Array

We are given an unsorted array nums and a positive integer k. Our goal is to find the element that would appear at index len(nums) - k if we sorted the entire array in ascending order (or equivalently, index k-1 if sorted descending).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Divide and Conquer#Heap

215. Kth Largest Element in an Array

Model: qwen3.5:9b
Topics: Divide and Conquer,Heap
FAANG asked: 1
Acceptance rate: 58.9%


Problem Breakdown

We are given an unsorted array nums and a positive integer k. Our goal is to find the element that would appear at index len(nums) - k if we sorted the entire array in ascending order (or equivalently, index k-1 if sorted descending).

Key constraints & details:

  • Duplicates allowed: The problem specifies “kth largest” not “distinct”. This means [3,2,1,5,6,4], k=2 -> sorted asc: [1,2,3,4,5,6] (answer 5), but if input was [3,2,3,...], duplicates count towards the rank.
  • Range: Values are between −104-10^4 and 10410^4. No overflow issues with standard integers in Python.
  • Input size: Up to 10410^4 elements (based on prompt constraints). This is small enough that even sorting passes, but we should aim for better than O(Nlog⁡N)O(N \log N) if possible when K<NK < N.

Intuition

The most straightforward approach is to sort the array and pick the element at index len(nums) - k. However, this takes O(Nlog⁡N)O(N \log N) time complexity because it sorts all elements when we only need one specific rank. This feels inefficient for large arrays where NN grows significantly larger than KK.

To optimize, consider that if we want the top k largest numbers, we don’t care about the smallest ones in the array. We can maintain a collection of exactly k elements representing our current “top k” candidates.

  • Min-Heap Approach: If we keep track of the smallest among these top k candidates using a Min-Heap (priority queue), any new number larger than this minimum should replace it to stay in the top k. The root of this heap will always be the smallest element within our set of largest elements, which is exactly what we need: the kkth largest overall.
  • QuickSelect Approach: Alternatively, using Divide and Conquer (like QuickSort’s partition), we can pick a pivot and rearrange the array so that all larger numbers are on one side. We then recurse only into the half containing our target rank. This gives expected linear time O(N)O(N).

Given Python’s standard library heapq, implementing the Min-Heap approach is robust, avoids recursion depth issues common in QuickSelect implementations for large inputs, and runs efficiently enough (O(Nlog⁡K)O(N \log K)). I will proceed with this solution but acknowledge that a custom partition-based implementation would achieve O(N)O(N).

Approach

  1. Initialize: Create an empty Min-Heap using heapq. In Python, the smallest element is at index 0 (root), which fits our need to track the “smallest of the largest”.
  2. Iterate: Loop through every number in nums.
  3. Maintain Heap Size: Push each number into the heap. If the heap size exceeds k, pop the smallest element (heapq.heappop). This ensures we only keep the KK largest elements seen so far, discarding anything smaller than our current threshold.
  4. Result: After processing all numbers, the root of the Min-Heap (the smallest among the top K) is the answer.

Complexity Analysis

  • Time Complexity: We iterate through nums once (NN operations). Each heap push/pop takes O(log⁡K)O(\log K) time. Total: O(Nlog⁡K)O(N \log K). This is better than sorting when K<NK < N. If we used QuickSelect, it would be expected O(N)O(N).
  • Space Complexity: We store at most k elements in the heap. Auxiliary space (ignoring input storage): O(K)O(K).

Solution

import heapq
from typing import List

def findKthLargest(nums: List[int], k: int) -> int:
    # Use a min-heap to keep track of the K largest elements seen so far.
    # The root will be the smallest among these, which is our target value.
    
    heap = []
    
    for num in nums:
        heapq.heappush(heap, num)
        
        # If we have more than k elements, remove the smallest one (root).
        if len(heap) > k:
            heapq.heappop(heap)
            
    # The root of the min-heap is now the Kth largest element.
    return heap[0]

# Example usage for verification
if __name__ == "__main__":
    print(findKthLargest([3,2,1,5,6,4], 2))      # Output: 5
    print(findKthLargest([3,2,3,1,2,4,5,5,6], 4))# Output: 4

Edge Cases Handled

  • Duplicates: The logic treats duplicates as distinct elements in the sorted order (e.g., [3, 2, 3], k=2 -> 3 is correct), which matches problem requirements.
  • k = len(nums): If KK equals array length, we push all items and pop none; heap root becomes smallest element of original set (which corresponds to index N-1 in sorted ascending). Correct.
  • Negative Numbers: Python handles integer comparison natively for negative values without overflow issues (O(N)O(N) logic holds regardless of sign).
  • k = 1: The heap will always contain the single largest number seen so far; root is that max value.