Скачать или смотреть 🔢 Find Kth Largest Element in an Array using Min Heap | Python Solution | No Sorting Needed 🚀

💡 Problem Statement:

Given an integer array nums and an integer k, the goal is to return the kth largest element in the array.

⚠️ Note that this means the kth element in sorted order, not necessarily distinct values.

🔍 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,2,2,3,3,4,5,5,6]. The 4th largest element is 4.
Efficient Approach: Min Heap (Priority Queue) – O(N log K) Complexity
We can solve this problem without sorting the entire array. Instead, we use a Min Heap with size k.

📌 Steps to Solve the Problem:

1️⃣ Use a Min Heap (heapq module in Python) to keep track of the top k largest elements.
2️⃣ Iterate through the array and push each element into the min heap.
3️⃣ If the heap size exceeds k, remove the smallest element.
4️⃣ Once all elements are processed, the smallest element in the heap is the kth largest in the array.

📌 Why does this work?

The min heap ensures that the smallest element (among the top k largest numbers) is at the root.
Since the heap only contains k elements at any time, the worst-case time complexity is O(N log K) instead of O(N log N) for sorting.

Python Code Implementation:

import heapq

class Solution:
def findKthLargest(self, nums, k):
min_heap = []

Build a min heap with the first k elements
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) v k:
heapq.heappop(min_heap) # Remove the smallest element

return min_heap[0] # The kth largest element

Example test cases

sol = Solution()
print(sol.findKthLargest([3,2,1,5,6,4], 2)) # Output: 5
print(sol.findKthLargest([3,2,3,1,2,4,5,5,6], 4)) # Output: 4

Complexity Analysis:

Building the heap takes O(K)
Processing each element (push + pop) takes O(log K)
Total Complexity: O(N log K), which is much faster than O(N log N) sorting.

Alternative Approaches:

✅ QuickSelect (Hoare's Selection Algorithm) – O(N) on average
✅ Sorting and Indexing – O(N log N), but not optimal

🎯 Use Cases:

✅ Efficiently finding the kth largest element in huge datasets
✅ Streaming data problems where elements arrive dynamically