DAY 72- 215. Kth Largest Element in an Array
Tags: leetcode, coding, algorithms, beginners
Published: 2023-08-14 18:05:19

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](https://leetcode.com/problems/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:

```cpp
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<int>() comparator. This ensures that the kth largest element will be at index k - 1 after the partial sort.



### Code:

```cpp

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](https://www.geeksforgeeks.org/priority-queue-in-cpp-stl/) 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:

```cpp
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:

| Algorithm | Time Complexity | Space Complexity |
|---|---|---|
| Max Heap                  | O(n + k log n) | O(k) |
| Partial Sorting           | O(n log k) | O(1) |
| Fully Sorting             | O(n log n) | O(1) |

---


Thanks for reading!. Feedback is highly appreciated!