K’th Smallest/Largest Element using STL

Software Development
#1

Hello Everyone,

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.

Examples:

Input : arr[] = {7, 10, 4, 3, 20, 15} k = 2 Output : 4 Smallest element is 3. Second smallest is 4. Input : arr[] = {7, 10, 4, 3, 3, 15} k = 2 Output : 4 Even if there are more than one occurrences of 3, answer should be 4. Input :arr[] = {7, 10, 4, 3, 20, 15} k = 4 Output : 10

We use set in C++ STL.

  1. Insert all elements into a set.
  2. Traverse the set and print k-th element.

// STL based C++ program to find k-th smallest

// element.

#include <bits/stdc++.h>

using namespace std;

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

{

// Insert all elements into the set

set< int > s;

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

s.insert(arr[i]);

// Traverse set and print k-th element

auto it = s.begin();

for ( int i = 0; i < k - 1; i++)

it++;

return *it;

}

int main()

{

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

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

cout << "K'th smallest element is "

<< kthSmallest(arr, n, k);

return 0;

}

Output:

K’th smallest element is 5

Time complexity of above solution is O(n Log n). Note that set in STL uses a self-balancing BST internally and therefore time complexity of search and insert operations is O(log n).