# K’th Smallest/Largest Element using STL

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
```

## Recommended: Please try your approach on {IDE} first, before moving on to the solution.

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

Related Posts :

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

This article is attributed to GeeksforGeeks.org

## tags:

Arrays Order-Statistics STL Arrays STL

code

load comments