Given an array arr[] and a number K, where K is smaller than the size of the array, we need to find the Kth smallest element in the given array. It is given that array elements can be repeated (not limited to distinct).
Examples:
Input: arr[] = {7, 10, 4, 3, 20, 15}, K = 3
Output: 7Input: arr[] = {7, 1, 5, 4, 20, 15, 8}, K = 5
Output: 8
We have discussed this article with other approaches as well:
- K’th Smallest/Largest Element in Unsorted Array
- K’th Smallest/Largest Element in Unsorted Array | Expected Linear Time
- K’th Smallest/Largest Element in Unsorted Array | Worst case Linear Time
Approach: The idea is to use the concept of Counting Sort. Below are the steps:
- Find the maximum element(say maxE) in the array and create an array(say freq[]) of length maxE + 1 and initialize it to zero.
- Loop through all the elements in the given array and store the frequency of the element in freq[].
- Iterate over the array freq[] until we reach the Kth element.
- Print the Kth element reached in the above step.
Below is the implementation of the above approach:
C++
// C++ program for the above approach #include <iostream> using namespace std; // Function to find the Kth smallest // element in Unsorted Array int findKthSmallest(int arr[], int n, int k) { // Initialize the max Element as 0 int max = 0; // Iterate arr[] and find the maximum // element in it for (int i = 0; i < n; i++) { if (arr[i] > max) max = arr[i]; } // Frequency array to store // the frequencies int counter[max + 1] = { 0 }; // Counter variable int smallest = 0; // Counting the frequencies for (int i = 0; i < n; i++) { counter[arr[i]]++; } // Iterate through the freq[] for (int num = 1; num <= max; num++) { // Check if num is present // in the array if (counter[num] > 0) { // Increment the counter // with the frequency // of num smallest += counter[num]; } // Checking if we have reached // the Kth smallest element if (smallest >= k) { // Return the Kth // smallest element return num; } } } // Driver Code int main() { // Given array int arr[] = { 7, 1, 4, 4, 20, 15, 8 }; int N = sizeof(arr) / sizeof(arr[0]); int K = 5; // Function Call cout << findKthSmallest(arr, N, K); return 0; } |
Java
// Java program for the above approach import java.io.*; class GFG { // Function to find the Kth smallest // element in Unsorted Array static int findKthSmallest(int[] arr, int n, int k) { // Initialize the max Element as 0 int max = 0; // Iterate arr[] and find the maximum // element in it for (int i = 0; i < n; i++) { if (arr[i] > max) max = arr[i]; } // Frequency array to store // the frequencies int[] counter = new int[max + 1]; // Counter variable int smallest = 0; // Counting the frequencies for (int i = 0; i < n; i++) { counter[arr[i]]++; } // Iterate through the freq[] for (int num = 1; num <= max; num++) { // Check if num is present // in the array if (counter[num] > 0) { // Increment the counter // with the frequency // of num smallest += counter[num]; } // Checking if we have reached // the Kth smallest element if (smallest >= k) { // Return the Kth // smallest element return num; } } return -1; } // Driver code public static void main(String[] args) { // Given array int[] arr = { 7, 1, 4, 4, 20, 15, 8 }; int N = arr.length; int K = 5; // Function call System.out.print(findKthSmallest(arr, N, K)); } } |
Python3
# Python3 program for the # above approach # Function to find the Kth # smallest element in Unsorted # Array def findKthSmallest(arr, n, k): # Initialize the max # Element as 0 max = 0 # Iterate arr[] and find # the maximum element in it for i in range(n): if (arr[i] > max): max = arr[i] # Frequency array to # store the frequencies counter = [0] * (max + 1) # Counter variable smallest = 0 # Counting the frequencies for i in range(n): counter[arr[i]] += 1 # Iterate through the freq[] for num in range(1, max + 1): # Check if num is present # in the array if (counter[num] > 0): # Increment the counter # with the frequency # of num smallest += counter[num] # Checking if we have reached # the Kth smallest element if (smallest >= k): # Return the Kth # smallest element return num # Driver Code if __name__ == "__main__": # Given array arr = [7, 1, 4, 4, 20, 15, 8] N = len(arr) K = 5 # Function Call print(findKthSmallest(arr, N, K)) # This code is contributed by Chitranayal |
C#
// C# program for the // above approach using System; using System.Collections.Generic; class GFG{ // Function to find the Kth smallest // element in Unsorted Array static int findKthSmallest(int[] arr, int n, int k) { // Initialize the max // Element as 0 int max = 0; // Iterate []arr and find // the maximum element in it for (int i = 0; i < n; i++) { if (arr[i] > max) max = arr[i]; } // Frequency array to store // the frequencies int[] counter = new int[max + 1]; // Counter variable int smallest = 0; // Counting the frequencies for (int i = 0; i < n; i++) { counter[arr[i]]++; } // Iterate through the []freq for (int num = 1; num <= max; num++) { // Check if num is present // in the array if (counter[num] > 0) { // Increment the counter // with the frequency // of num smallest += counter[num]; } // Checking if we have reached // the Kth smallest element if (smallest >= k) { // Return the Kth // smallest element return num; } } return -1; } // Driver code public static void Main(String[] args) { // Given array int[] arr = {7, 1, 4, 4, 20, 15, 8}; int N = arr.Length; int K = 5; // Function call Console.Write(findKthSmallest(arr, N, K)); } } // This code is contributed by shikhasingrajput |
Javascript
<script> // JavaScript program for the above approach // Function to find the Kth smallest // element in Unsorted Array function findKthSmallest(arr, n, k) { // Initialize the max Element as 0 let max = 0; // Iterate arr[] and find the maximum // element in it for (let i = 0; i < n; i++) { if (arr[i] > max) max = arr[i]; } // Frequency array to store // the frequencies let counter = Array.from({length: max + 1}, (_, i) => 0); // Counter variable let smallest = 0; // Counting the frequencies for (let i = 0; i < n; i++) { counter[arr[i]]++; } // Iterate through the freq[] for (let num = 1; num <= max; num++) { // Check if num is present // in the array if (counter[num] > 0) { // Increment the counter // with the frequency // of num smallest += counter[num]; } // Checking if we have reached // the Kth smallest element if (smallest >= k) { // Return the Kth // smallest element return num; } } return -1; } // Driver Code // Given array let arr = [ 7, 1, 4, 4, 20, 15, 8 ]; let N = arr.length; let K = 5; // Function call document.write(findKthSmallest(arr, N, K)); // This code is contributed by sanjoy_62. </script> |
Output
8
Time complexity: O(N+MaxElement) where N is the number of elements in the given array, and MaxElement is the maximum number in the array. Pseudo Linear-Time complexity.
Auxiliary Space: O(M) where M is the maximum element in the given array.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
