Hello Everyone,
Given an array and a number k where k is smaller than the size of the array, we need to find the k’th smallest element in the given array. It is given that all array elements are distinct.
Examples:
Input : arr = {7, 10, 4, 3, 20, 15}
k = 3
Output : 7Input : arr = {7, 10, 4, 3, 20, 15}
k = 4
Output : 10
Method (Simple Solution)
A simple solution is to sort the given array using a O(N log N) sorting algorithm like Merge Sort, Heap Sort, etc., and return the element at index k-1 in the sorted array.
Time Complexity of this solution is O(N Log N)
- C++
// Simple C++ program to find k'th smallest element
#include <algorithm>
#include <iostream>
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 program to test above methods
int main()
{
int arr[] = { 12, 3, 5, 7, 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
There are two more solutions which are better than above discussed ones. Do try it on your own and find more efficient way and share it in the reply section below. Please give feedback as it helps me improving and learning more new things, ways to solve the problems.
Thankyou.
Keep Learning.