Finding Kth Largest Number in a Given Array of Large Numbers

Ujjawal Gupta
Last Updated: May 13, 2022

Introduction

In this blog, we will discuss a problem based on Sorting in which we are asked to find the K-th largest number of the given array of large numbers. Sorting-based coding problems are widely asked in competitive programming contests and in various coding interviews. Here we will discuss the most efficient approach to achieve the result.

The Problem Statement

Suppose you are given an integer ‘K’ and a string array of size ‘N’ where each string may represent a very large number up to 100 digits. Your task is to print the Kth largest number present in the array.

For example, given an array ARR = { “213”  “34”  ”566” “74” ”22”} and we need to find the 2nd largest number present in this array. In this case, 566 is the largest number, and 213 is the 2nd largest number. Hence 213 is our answer.

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;
}

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.

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. 

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

 

Was this article helpful ?
0 upvotes