kthLargestSmallestElement.cpp

#include<iostream>
#include<limits>
using namespace std;


/*

Given an array and a number k where k is smaller than size of array, we need to find the k’th smallest element in the given array. It is given that ll array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}
       k = 4
Output: 10



*/

void merge(int *Arr, int start, int mid, int end) {
	// create a temp array
	int temp[end - start + 1];

	// crawlers for both intervals and for temp
	int i = start, j = mid+1, k = 0;

	// traverse both arrays and in each iteration add smaller of both elements in temp 
	while(i <= mid && j <= end) {
		if(Arr[i] <= Arr[j]) {
			temp[k] = Arr[i];
			k += 1; i += 1;
		}
		else {
			temp[k] = Arr[j];
			k += 1; j += 1;
		}
	}

	// add elements left in the first interval 
	while(i <= mid) {
		temp[k] = Arr[i];
		k += 1; i += 1;
	}

	// add elements left in the second interval 
	while(j <= end) {
		temp[k] = Arr[j];
		k += 1; j += 1;
	}

	// copy temp to original interval
	for(i = start; i <= end; i += 1) {
		Arr[i] = temp[i - start];
	}
}

// Arr is an array of integer type
// start and end are the starting and ending index of current interval of Arr

void mergeSort(int *Arr, int start, int end) {

	if(start < end) {
		int mid = (start + end) / 2;
		mergeSort(Arr, start, mid);
		mergeSort(Arr, mid+1, end);
		merge(Arr, start, mid, end);
	}
}


int Klargest(int *arr,int size , int k){

    return arr[size-k];
}

int Ksmallest(int *arr,int k){


    return arr[k-1];    

}
int main(){
    long long int size,k;
    cin>>size;
    int * arr = new int[size];

    for(int i = 0 ; i < size ; i++){
        cin>>arr[i];
    }
    cin>>k;

    mergeSort(arr,0,size-1);
    int largest = Klargest(arr,size,k);
    int smallest = Ksmallest(arr,k);

    cout<<"The kth largest element is "<<largest<<endl;
    cout<<"The kth smallest element is "<<smallest<<endl;

}