🙏

জয়  শ্রী  রাম

🕉

---

Problem Statement:

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

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

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

Solution:

This is a great beginner level problem to show you the potential of heap data structure.

To solve this problem, we could sort the given array and return the k^th element. But that would be O(nlogn) algorithm where n = total number of elements in the given array. Can we do better ? Definitely. Use Heap data structure.

Think of the solution like this: Store the k largest elements and return the minimum of these k largest elements. This would give you the k^th largest element. This could be implemented very efficiently using min heap. We iterate over the given array from index = 0 to (n - 1) and for all index i such that i >= k and i < n, where n = total number of elements in the given array, we maintain a min heap of size k which would contain the largest k elements in arr[0...(i - 1)], where arr is the given array. So, when we reach index (n - 1) while iterating from index 0 to index (n - 1), the min heap would contain k largest elements of the given array. At this point the root of the min heap would contain the k^th largest element in the given array. So we return the min element from the min heap.

To maintain the size of the min heap to be not more than k at any point of time, once we have already gotten k elements in the min heap, we do a remove min operation for every new element added. That way we are getting rid of the minimum element in the min heap and keeping the largest elements.

Using heap data structure improves the time complexity from O(nlogn) to O(nlogk).

The code below implements the algorithm discussed above:



Login to Access Content

Complexity Analysis:

• Time complexity: O(Nlogk), where N = total number of elements. Insertion and deletion from min heap is O(logk) since min heap has k elements. We do insertion for N elements and remove min for (N - k) elements.
• Space complexity: O(k), since the heap would have k elements.

Instructor: