Program to Find Kth Smallest Element of an Array.

Given an array of n distinct elements and we need to find the kth smallest element from the given array where the value of k is larger than the size of the given array.

Example:

Input: arr[] = {12, 9, 2, 7, 3, 10}, k = 2
Output: 3

Input: arr[] = {12, 9, 2, 7, 3, 10}, k = 5
Output: 10

There are multiple ways in which you can solve this basic level array problem and here we are going to discuss two different ways to find the kth smallest element of an array.

Approach 1: Using Sorting.

The brute force approach that we can think of is to sort the given array in ascending order and return the element present at index (k-1) and array elements are stored based on 0-based indexing. You can use the Quick sort algorithm to sort the array whose time complexity is O(nlogn).

In C++, we have one sort member function that sorts the array in ascending order by default and the internally implemented quick sort algorithm.

C++ Code Implementation:

//C++ code to find the kth smallest element of an array
#include<iostream>
#include<algorithm>
using namespace std;

//function to return kth smallest element
int smallestNumber(int arr[], int n, int k){
    //sort the array
    sort(arr, arr+n);

    return arr[k-1];
}

int main(){
    
    int arr[] = {12, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 2;
    cout<<"The kth smallest element is: "<<smallestNumber(arr, n, k); 

    return 0;
}

Output:

The kth smallest element is: 3

Time Complexity: O(nlogn)
Space Complexity: O(1)

Approach 2: Using Set data structure.

The set data structure is used to store unique elements of same type in sorted order. As mentioned in the question itself that all elements are distinct which means if we store them in a set data structure we can easily find the kth smallest element.

The drawback of using set data structure is that we required n extra spaces to sort the given array which increase the space complexity to O(n).

C++ Code Implementation:

//C++ code to find kth smallest element of an array using set
#include<bits/stdc++.h>
using namespace std;

//function to return kth smallest element
int smallestNumber(int arr[], int n, int k){
    //set data structure
    set<int> s(arr, arr+n);
    //pointer to first element
    set<int>::iterator it = s.begin();
    advance(it, k-1);

    return *it;
}

int main(){
    
    int arr[] = {12, 9, 2, 7, 3, 10};
    //size of given array
    int n = sizeof(arr)/sizeof(arr[0]);
    int k = 5;
    cout<<"The kth smallest element is: "<<smallestNumber(arr, n, k); 

    return 0;
}

Output:

The kth smallest element is: 10

Time Complexity: O(nlogn)
Space Complexity: O(n)

Next: (getButton) #text=(Program to Find Kth Largest Element of an Array) #icon=(link) #color=(#2339bd)

Program to Find Kth Smallest Element of an Array.

Approach 1: Using Sorting.

Approach 2: Using Set data structure.

No comments:

Post a Comment