Finding Kth Largest Number in a Given Array of Large Numbers

Approach 

The naive approach to solving this problem is converting all the strings to integers and then sorting the array and returning the kth largest integer. This approach is good for small numbers, but if the size of the string exceeds 18, then this approach fails as the range of long is 10^18, as it is not possible to convert such strings to integers.

The correct approach to solve this problem is based on the Greedy Algorithm. Here we sort all the strings bypassing the custom compare function in our sort function.

Algorithm

• Create custom function ‘cmp’ which takes two strings.
• If the value of the 1st string is greater than the 2nd one, then return the 1st one else, return the 2nd one.
• Pass this custom function in our inbuilt sort function as the third argument.
• Call the sort function.
• Print the Kth value of the array.

Program

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

// Custom function to overload the sort function.
bool cmp(string &s1, string &s2)
{
   // if both the strings have the same length then return max.
   if (s1.size() == s2.size())
       return s1 > s2;

   // if both the strings have different lengths.
   return s1.size() > s2.size();
}

// Function to find the Kth largest number in the vector of strings.
void Kthlargest(int n, int k, vector<string> &vec)
{
   // Sort the vector by passing a custom function.
   sort(vec.begin(), vec.end(), cmp);

   string largest = vec[k - 1];

   // Printing the K-th largest number in the array.
   cout << largest;
}
int main()
{
   // Variable 'N' to store the number of elements in the array and variable 'K' to indicate the Kth largest number.
   int n, k;

   cin >> n;

   // Declaring vector of size 'N'.
   vector<string> vec(n);

   // Taking vector input.
   for (int i = 0; i < n; i++)
       cin >> vec[i];

   cin >> k;

   // Calling function 'Kthlargest()';
   Kthlargest(n, k, vec);
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Input

7
70 40 100 10 55 85 120
3

Output

85

Time Complexity

O(N * Log(N)), where ‘N’ is the size of the array. 

As sorting of the array of size ‘N’ takes O(N * log(N)) time.

Also Read - Selection Sort in C

Space Complexity

O(1).

As we don’t use any extra space except a few constants.

Key Takeaways

In this blog, we have learned how to create a custom function to sort the vector. Also, we have learned how to pass a custom function in our sort function. 

Recommended Problems - 

• Sort 0 1 2 
• Wiggle sort
• Find first and last position in sorted array

If you want to explore more on such topics then head over to our practice platform Coding Ninjas Studio to practice top problems, attempt mock tests, read interview experiences, and much more. Till then, Happy Coding!