Program to Find Kth Largest Element of an Array.

Given an array of n distinct elements and we need to find the kth largest number from the given array where the value of k is larger than the size of the given array.

Example:

Input: arr[] = {4, 9, 2, 7, 3, 10}, k = 3
Output: 7

Input: arr[] = {4, 9, 2, 7, 3, 10}, k = 5
Output: 3

Approach 1: Using Sorting.

The simplest approach that anyone can think of is to sort the given array in ascending order and return the element present at index (n-k) and array elements are stored based on 0-based indexing. You can use the sort function given in almost all programming languages or you can use quick sort whose time complexity is O(nlogn).

C++ Code Implementation:

//C++ code to find the kth largest element of an array
#include<iostream>
#include<algorithm>
using namespace std;

//function to return kth largest element
int largestNumber(int arr[], int n, int k){
    //sort the array
    sort(arr, arr+n);

    return arr[n-k];
}

int main(){
    
    int arr[] = {4, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 3;
    cout<<"The kth largest element is: "<<largestNumber(arr, n, k); 

    return 0;
}

Output:

The kth largest element is: 7

Time Complexity: O(nlogn)
Space Complexity: O(1)

Approach 2: Using Set data structure.

The set data structure is used to store unique elements same type in sorted order. As mentioned in the question itself that all elements are distinct which means if we store them in a set data structure we can easily find the kth largest element.

C++ Code Implementation:

//C++ code to find kth largest element of an array using set
#include<bits/stdc++.h>
using namespace std;

//function to return kth largest element
int largestNumber(int arr[], int n, int k){
    //set data structure
    set<int> s(arr, arr+n);
    //pointer to first element
    set<int>::iterator it = s.begin();
    advance(it, n-k);

    return *it;
}

int main(){
    
    int arr[] = {4, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout<<"The kth largest element is: "<<largestNumber(arr, n, k); 

    return 0;
}

Output:

The kth largest element is: 9

Time Complexity: O(nlogn)
Space Complexity: O(n)

Next: (getButton) #text=(Program to Find Kth Smallest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Find Kth Largest Element of an Array.

Approach 1: Using Sorting.

Approach 2: Using Set data structure.

No comments:

Post a Comment