kth Largest Element in an Array


Given an array of positive integers. Find the n(th) largest element in the array.


Sort the array in decreasing order then loop through the sorted array while counting unique elements then stop when the count is equal to (n). In the code below we will assume the array is already sorted. You can refer to the following post for more information about merge sort which you can use to efficiently sort the array in O(nlogn) time complexity


Here is the C++ code to do that assuming the array is already sorted in decreasing order

#include <iostream>

using namespace std;

//Main function
void main()
	//Input array (already sorted)
	int A[] = {6, 6, 5, 5, 5, 4, 3, 3, 2, 1};

	//Array size
	int s = 10;

	//Let us assume we need to find the 3d
	//maximum which is 4
	int n = 3;

	int c = 1;

	//Initialize n(th) max
	int nmax = A[0];

	//Loop in the array while the count is less than (n)
	for (int i = 0; i < s && c < n; i++)
		//If the current array element is different
		//from the current n(th) max increment the
		if (A[i] != nmax) c++;

		//Update n(th) max
		nmax = A[i];

	//Once the loop above is finished
	//then n(th) max will be already calculated
	cout << nmax << endl;
Tags:, ,

Leave a Reply