You are given an unsorted array, and a key number, find the largest number of that key position.

array = { 3, 7, 6, 5, 2, 9, 4}
key = 3

Solution = 6.

Question explanation:

First sort the above array:

{2, 3, 4, 5, 6, 7, 9}

So the keyth largest element is “6”.
Because 9 is first largest
Because 7 is second largest
Because 6 is third largest

Solution explanation:

We can solve this by 3 different ways:

1. STL sorting

2. priority_queue

3. Implementing our own sorting.

Solution in C++

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

int find_key_th_largest_element_using_inbuit_sort(vector<int> arr, int key )
{
	sort(arr.begin(), arr.end(), [](int &a, int &b){return a>b;});
	return arr[key-1];
}
    
int find_key_th_largest_element_using_priority_queue(vector<int>& arr, int key) 
{
	priority_queue<int> pq(arr.begin(), arr.end());
	for (int i = 0; i < key - 1; i++) 
	{
		pq.pop();
	}
	return pq.top();
}

int find_key_th_largest_element_using_sort(vector<int>& arr, int key) 
{
    for(int i = 0; i < key; i++)
    {
        int temp_max = i;
        for(int j = i+1; j < arr.size(); ++j)
            if(arr[j] > arr[temp_max]) temp_max = j;
        swap(arr[i], arr[temp_max]);
    }
    return arr[key-1];
}

int main()
{
	vector<int> arr = {4, 5, 6, 1, 2, 3, 9};
	int key = 2;

	cout<<"Solution using inbuilt sort = "<<find_key_th_largest_element_using_inbuit_sort(arr, key)<<endl;
	cout<<"Solution using priority queue = "<<find_key_th_largest_element_using_priority_queue(arr, key)<<endl;
	cout<<"Solution using sort = "<<find_key_th_largest_element_using_sort(arr, key)<<endl;

	return 0;
}

Output:

Solution using inbuilt sort = 6
Solution using priority queue = 6
Solution using sort = 6