# K’th Smallest/Largest Element using STL

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), 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).