DAY 72- 215. Kth Largest Element in an Array

Hey Guys! Today we are on the 72nd day and we are going to solve today's daily leetcode problem. The question today is pretty clear so we will jump straight to approaches.

Question: 215. Kth Largest Element in an Array

Problem Description

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.

Note: Can you solve it without sorting?

Example 1:

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

Sorting Approach:

The sorting approach which first comes to our mind deals with sorting the original array. Since we have to return the value of kth largest not it's index, (if there are duplicates) our sorting approach works here. This will put the kth sorted character at it's place so we can return it.

Code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int n = nums.size();
        sort(nums.begin(),nums.end());
        return nums[n-k];
    }
};

Approach using Partial Sort

This approach utilizes the inbuilt library of C++, which gives us an inbuilt function to partially sort an array. We can also write it's code but I am going to use it here for algorithm purposes.

The partial_sort function is utilized to partially sort the first k elements of the nums vector. The sorting is performed in descending order using the greater() comparator. This ensures that the kth largest element will be at index k - 1 after the partial sort.

Code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
        return nums[k - 1];
    }
};

Priority Queue/Max Heap Approach:

We use a priority_queue to build a max heap. It is initialized with the elements from the nums vector. As the priority_queue is a max heap by default, the largest element will always be at the top (root) of the heap.

Incase you don't know what max heap is , I suggest reading this article on it.

To find the kth largest element, we iteratively remove elements from the heap using the pop operation k-1 times. After performing these removals, the kth largest element will be at the top of the heap because Max Heap is maintained this way.

Code:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int> pq(nums.begin(),nums.end()); //insert all elements into priority queue
        for(int i = 0; i < k-1; i++){
            pq.pop(); //pop all the elements until last kth element largest is left at the top
        }
        return pq.top(); //return it
    }
};

Complexity Analysis:

Thanks for reading!. Feedback is highly appreciated!