# AlgoMaster Sheet – Kth Largest Element In An Array

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

Example 2:

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

#### Solution

Disclaimer: Don’t jump directly to the solution, try it out yourself first.

`Practice Questions   Kth Smallest Element in the Array`

### Solution 1: Sorting the Array

The most naive approach:

• To sort the given array in descending order.
• The index of kth Largest element = k-1 ( zero-based indexing )
• The array can also be sorted in ascending order.
• The index of kth Largest element = n-k

Time Complexity: O(NlogN), where N is the size of the array.
Space Complexity: O(1), since no additional space is used.

```#include <bits/stdc++.h>
using namespace std;

void findKthLargest(vector<int> &nums, int k)
{
//sort the array
sort(nums.begin(), nums.end());
int n = nums.size();    //array size

cout << "kth Largest element " << nums[n - k] <<endl;
}

int main()
{

vector<int> nums = {3,2,1,5,6,4};

findKthLargest(nums, 2);

return 0;
}```

#### Output:

kth Largest element 5

### Solution 2: Using Heap

• Initialise a max-heap.
• Insert all the elements of the given array into the max heap.
• Since the top element of the max-heap is the largest element of the heap , we will remove the top K-1 elements from the heap .  The top element will be Kth Largest element.
• To get the Kth Smallest element , we will use a min-heap . After removal of top k-1 elements , the Kth Smallest element is top of the Priority queue.

Time Complexity: O(K + (N – K) * log(K) ), where N is size of the array.
Space Complexity: O(K), since the heap is used.

```#include <bits/stdc++.h>
using namespace std;

int findKthLargest(vector<int> &nums, int k)
{
for (auto number : nums)
{
}
int resultant = 0;
while (k--)
{
}

return resultant;
}

int main()
{

vector<int> nums = {3, 2, 1, 5, 6, 4};

cout << "kth Largest element: " << findKthLargest(nums, 2) << endl;

return 0;
}```

#### Output:

kth Largest element 5

To master AlgoMaster Sheet – Kth Largest Element In An Array in the most efficient and effective way, do check out this:

`This article is contributed by : Sayan Dutta to this article on csforall.in`