K-th Smallest/Largest element in an Unsorted Array | Algorithms - Computer Science Engineering (CSE) PDF Download

Problem Statement

Given an array arr[] of N distinct elements and a number K, where K is smaller than the size of the array. Find the K’th smallest element in the given array.

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 

Approaches to find K’th smallest element in unsorted array

1. [Naive Approach] Using Sorting 

The very basic approach is to sort the given array and return the element at the index K – 1.

// C++ program to find K'th smallest element

#include <bits/stdc++.h>

using namespace std;

// Function to return K'th smallest element in a given array

int kthSmallest(int arr[], int N, int K)

{

    // Sort the given array

    sort(arr, arr + N);

    // Return k'th element in the sorted array

    return arr[K - 1];

}

// Driver's code

int main()

{

    int arr[] = { 12, 3, 5, 7, 19 };

    int N = sizeof(arr) / sizeof(arr[0]), K = 2;

    // Function call

    cout << "K'th smallest element is "

         << kthSmallest(arr, N, K);

    return 0;

}

Output:

K'th smallest element is 5

Time Complexity: O(N log N)
Auxiliary Space: O(1) 

2. Using Priority Queue(Max-Heap) – O(N * log(K)) time and O(K) auxiliary space:

The intuition behind this approach is to maintain a max heap (priority queue) of size K while iterating through the array. Doing this ensures that the max heap always contains the K smallest elements encountered so far. If the size of the max heap exceeds K, remove the largest element this step ensures that the heap maintains the K smallest elements encountered so far. In the end, the max heap’s top element will be the Kth smallest element.

#include <bits/stdc++.h>

using namespace std;

// Function to find the kth smallest array element

int kthSmallest(int arr[], int N, int K)

{

    // Create a max heap (priority queue)

    priority_queue<int> pq;

    // Iterate through the array elements

    for (int i = 0; i < N; i++) {

        // Push the current element onto the max heap

        pq.push(arr[i]);

        // If the size of the max heap exceeds K, remove the largest element

        if (pq.size() > K)

            pq.pop();

    }

    // Return the Kth smallest element (top of the max heap)

    return pq.top();

}

// Driver's code:

int main()

{

    int N = 10;

    int arr[N] = { 10, 5, 4, 3, 48, 6, 2, 33, 53, 10 };

    int K = 4;

    // Function call

    cout << "Kth Smallest Element is: "

         << kthSmallest(arr, N, K);

}

Output:

Kth Smallest Element is: 5

Time Complexity: O(N * log(K))

The approach efficiently maintains a container of the K smallest elements while iterating through the array, ensuring a time complexity of O(N * log(K)), where N is the number of elements in the array.
Auxiliary Space: O(K)

3.Using Counting Sort (Not efficient for large range of elements)

Counting sort is a linear time sorting algorithm that counts the occurrences of each element in an array and uses this information to determine the sorted order. The idea behind using counting sort to find the K’th smallest element is to use the counting phase, which essentially calculates the cumulative frequencies of elements. By tracking these cumulative frequencies, we can efficiently determine the K’th smallest element.

Note: This approach is particularly useful when the range of elements is small, this is because we are declaring a array of size maximum element. If the range of elements is very large, the counting sort approach may not be the most efficient choice.

#include <iostream>

using namespace std;

// This function returns the kth smallest element in an array

int kthSmallest(int arr[], int n, int k) {

    // First, find the maximum element in the array

    int max_element = arr[0];

    for (int i = 1; i < n; i++) {

        if (arr[i] > max_element) {

            max_element = arr[i];

        }

    }

    // Create an array to store the frequency of each 

   // element in the input array

    int freq[max_element + 1] = {0};

    for (int i = 0; i < n; i++) {

        freq[arr[i]]++;

    }

    // Keep track of the cumulative frequency of elements 

   // in the input array

    int count = 0;

    for (int i = 0; i <= max_element; i++) {

        if (freq[i] != 0) {

            count += freq[i];

            if (count >= k) {

                // If we have seen k or more elements, 

              // return the current element

                return i;

            }

        }

    }

    return -1;

}

// Driver Code

int main() {

    int arr[] = {12,3,5,7,19};

    int n = sizeof(arr) / sizeof(arr[0]);

    int k = 2;

    cout << "The " << k << "th smallest element is " << kthSmallest(arr, n, k) << endl;

    return 0;

}

Output

The 2th smallest element is 5.

Time Complexity: O(N + max_element), where max_element is the maximum element of the array.
Auxiliary Space: O(max_element)