Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++

Published: 01 January 1970
on channel: Prateek Jain Academy

705

K’th Smallest/Largest Element in Unsorted Array

Download our App : - https://eduthanos.page.link/t2yA

Contact No - 9555031137

www.PrateekJainAcademy.com

Given an array and a number K where K is smaller than the size of the array. Find the K’th smallest element in the given array. Given that all array elements are distinct.

Examples:

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Output: 7

Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 4
Output: 10

K’th smallest element in an unsorted array using sorting:
Sort the given array and return the element at index K-1 in the sorted array.

Follow the given steps to solve the problem:

Sort the input array in the increasing order
Return the element at the K-1 index (0 – Based indexing) in the sorted array

K’th smallest element in an unsorted array using set data structure:
Set data structure can be used to find the kth smallest element as it stores the distinct elements in sorted order. Set can be used because it is mentioned in the question that all the elements in the array are distinct.

Follow the given steps to solve the problem:

Insert all array elements into the set
Advance the iterator to the Kth element in the set
Return the value of the element at which the iterator is pointing

K’th smallest element in an unsorted array using Min-Heap
Min-Heap can be used to find the kth smallest element, by inserting all the elements into Min-Heap and then and call extractMin() function K times.

Follow the given steps to solve the problem:

Insert all the array elements into the Min-Heap
Call extractMin() function K times
Return the value obtained at the last call of extractMin() function

Max-Heap can be used to find the kth smallest element, by inserting first K elements into Max-Heap and then compare remaining elements with the root of the Max-Heap and if the element is less than the root then remove the root and insert this element into the heap and finally return root of the Max-Heap

Follow the given steps to solve the problem:

Build a Max-Heap MH of the first K elements (arr[0] to arr[K-1]) of the given array.
For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of MH.
If the element is less than the root then make it the root and call heapify for Max-Heap MH
b) Else ignore it.
Finally, the root of the MH is the Kth smallest element.

To find the Kth minimum element in an array, insert the elements into the priority queue until the size of it is less than K, and then compare remaining elements with the root of the priority queue and if the element is less than the root then remove the root and insert this element into the priority queue and finally return root of the priority queue

Follow the given steps to solve the problem:

Build a priority queue of the first K elements (arr[0] to arr[K-1]) of the given array.
For each element, after the Kth element (arr[K] to arr[n-1]), compare it with the root of priority queue.
If the element is less than the root then remove the root and insert this element into the priority queue
b) Else ignore it.
Finally, the root of the priority queue is the Kth smallest element.

On this page of the site you can watch the video online Program 9 - Kth smallest/largest element in Array | Competitive Programming in C++ with a duration of hours minute second in good quality, which was uploaded by the user Prateek Jain Academy 01 January 1970, share the link with friends and acquaintances, this video has already been watched 705 times on youtube and it was liked by 19 viewers. Enjoy your viewing!