Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
The Problem Statement
3.
Approach 
4.
Algorithm
4.1.
Input
4.2.
Output
5.
Time Complexity
6.
Space Complexity
Last Updated: Mar 27, 2024

Finding Kth Largest Number in a Given Array of Large Numbers

Author Ujjawal Gupta
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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.

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 - 


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!

 

Previous article
Find Maximum Meetings in One Room
Next article
Count Strings that Do Not Contain Any Alphabet’s Both Uppercase and Lowercase
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass