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.

- Insert all elements into a set.
- 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).