kth Largest Element in an Array

Problem

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

Solution

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

Code

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

//Includes
#include <iostream>

//STD
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;

	//Counter
	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
		//counter
		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