Find the "Kth" max and min element of an array - 450DSA Cracker Solution

Kth smallest element

Given an array arr[] and an integer K where K is smaller than size of array, the task is to find the K^th smallest element in the given array. It is given that all array elements are distinct.

Note :- l and r denotes the starting and ending index of the array.

Example 1:

Input:
N = 6
arr[] = 7 10 4 3 20 15
K = 3
L=0 R=5

Output : 7
Explanation :
3rd smallest element in the given 
array is 7.

Example 2:

Input:
N = 5
arr[] = 7 10 4 20 15
K = 4 L=0 R=4
Output : 15
Explanation :
4th smallest element in the given 
array is 15.

Your Task:
You don't have to read input or print anything. Your task is to complete the function kthSmallest() which takes the array arr[], integers l and r denoting the starting and ending index of the array and an integer K as input and returns the K^th smallest element.

Expected Time Complexity: O(n*log(n) )

Expected Auxiliary Space: O(log(n))

Code

Solution 1:

int kthSmallest(int arr[], int l, int n, int k) { int max_element = arr[0];
    for (int i = 1; i <= n; i++) {
        if (arr[i] > max_element) {
            max_element = arr[i];
        }
    }
     int freq[max_element + 1] = {0};
    for (int i = 0; i <= n; i++) {
        freq[arr[i]]++;
    }    int count = 0;
    for (int i = 0; i <= max_element; i++) {
        if (freq[i] != 0) {
            count += freq[i];
            if (count >= k) {
                return i;
            }
        }
    }
    return -1; //code here
    }

Solution 2

int max = arr[0];
        for(int i=0;i<=n;i++)
        {
            if(arr[i] > max)
                max= arr[i];
        }
        int freq[max +1 ] ={0}, output[n] ,count=0;
        for(int i=0;i<=n ;i++)
            ++freq[arr[i]];

        for(int i=1;i<=max;i++)
            freq[i] = freq[i] + freq[i-1];
        for(int i=0;i<=n;i++)
        {
            output[freq[arr[i]] -1] = arr[i];
        }

        if (k > n+1) return -1;
        else return output[k-1];

Solution 3

priority_queue <int> pq;
        for(int i=l;i<=r;i++)
        {
            if(pq.size() == k )
            {
                if(pq.top() > arr[i]){
                    pq.pop();
                    pq.push(arr[i]);
                }
            }
            else
            {
                pq.push(arr[i]);
            }
        }
        return pq.top();