Kth Largest Element in an Array – LeetCode75 Python Solution Explained

The Kth Largest Element in an Array problem (LeetCode75) is a classic heap-based problem frequently asked in coding interviews. It tests your understanding of priority queues, heaps and efficient element selection.

In this blog, we will break down the problem, provide examples, explain the Python solution step by step with code snippets, analyze time and space complexity, discuss edge cases and explore real-world applications.

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.

Example 1

Input:

nums = [3,2,1,5,6,4], k = 2

Output:

5

Explanation: The sorted array is [1,2,3,4,5,6]. The 2nd largest element is 5.

Example 2

Input:

nums = [3,2,3,1,2,4,5,5,6], k = 4

Output:

4

Explanation: The sorted array is [1,1,2,2,3,3,4,5,5,6]. The 4th largest element is 4.

Complete Python Solution

import heapq
from typing import List

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

        # Initialize heap with first k elements
        for i in range(k):
            heapq.heappush(min_heap, nums[i])

        # Process remaining elements
        for i in range(k, len(nums)):
            if nums[i] > min_heap[0]:
                heapq.heappop(min_heap)
                heapq.heappush(min_heap, nums[i])
                
        return min_heap[0]

Step-by-Step Explanation

Step 1: Initialize Min-Heap

We create a min-heap of size k with the first k elements. The top of the heap will always be the smallest element in the heap.

min_heap = []
for i in range(k):
    heapq.heappush(min_heap, nums[i])

Step 2: Process Remaining Elements

For every remaining element in the array, check if it is larger than the smallest in the heap. If yes, replace it to maintain the k largest elements in the heap.

for i in range(k, len(nums)):
    if nums[i] > min_heap[0]:
        heapq.heappop(min_heap)
        heapq.heappush(min_heap, nums[i])

Step 3: Return Kth Largest

After processing all elements, the top of the min-heap is the kth largest element.

return min_heap[0]

Time and Space Complexity

• Time Complexity:O(n log k)
  • Each heap operation (heappush or heappop) takes O(log k).
  • We perform n operations in total.
• Space Complexity:O(k)
  • The min-heap stores k elements.

Edge Cases

1. All elements are equal: The heap will contain the same repeated element.
2. k equals 1: Returns the largest element.
3. k equals n: Returns the smallest element.
4. Array contains negative numbers: Works correctly since heap comparisons handle negative values.

Real-World Applications

• Streaming Data: Find the kth largest value in a stream of numbers.
• Leaderboard Rankings: Maintain top k scores efficiently.
• Financial Data: Determine kth largest transactions or stock prices.
• Resource Management: Find kth highest usage in systems monitoring.

Conclusion

The Kth Largest Element in an Array problem is a classic use case for heap-based selection. By maintaining a min-heap of size k, we efficiently track the k largest elements and can retrieve the kth largest in O(n log k) time.

This approach is optimal for large datasets where sorting the entire array would be less efficient.

Related Reads

• Rotting Oranges – LeetCode75 Python Solution Explained
• Delete Node in a Binary Search Tree – LeetCode75 Python Solution Explained
• Number of Provinces – LeetCode75 Python Solution Explained
• Binary Tree Right Side View – LeetCode75 Python Solution Explained
• Leaf-Similar Trees – LeetCode75 Python Solution Explained

References

1. LeetCode – Kth Largest Element in an Array
2. Heap Data Structure – GeeksforGeeks
3. Priority Queue in Python