Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email
Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!
Arrays

Kth Smallest Element in an Array

Naman Kukreja

Last Updated on April 19, 2023 by Abhishek Sharma

An array is a data structure used in computer programming to store a collection of values, each with its own unique index or key. These values can be of any data type, such as integers, characters, or objects. Arrays allow for efficient access to and manipulation of individual elements, making them a common tool for organizing and processing data. Arrays can be one-dimensional, where values are stored in a linear sequence, or multi-dimensional, where values are organized in a grid-like structure. The size of an array is fixed when it is created, and elements can be added or removed using built-in functions. Arrays are a fundamental concept in many programming languages and are widely used in a variety of applications. The elements can be present in any order and we will find the kth smallest element in an array.

Kth Smallest Element in an Array

Given an array of integer type containing n elements, we have to find the kth smallest element in an array. With the condition given that all the elements in the array are distinct. And the value of k will be less than equal to n where n is the number of elements in the array.

Examples to Understand

Here we will look at some of the examples corresponding to the question of finding the kth smallest element in an array.

Input

A[]={1, 5,7,16,2,4,3,77}
 k=3

Output:

The 3rd smallest element of the above array is 3.

Input

A[]={11, 52,7,146,24,44,3,46,75,23,42}
 k=4

Output:

The 4th smallest element of the above array is 23.

Different Methods to Find Kth Smallest Element of an Array

Now we will discuss various approaches to solve the above problem i,e, find the kth smallest element in an array.

Approach 1: Brute Force using Sorting

In this approach, we will see the solution to the question of finding the kth smallest element in an array using sorting.
As the name suggests it is simple to approach we will just sort the array and after that, we will find the kth element from the start of the array i.e, from the left.

Algorithm
Here we will discuss the steps one needs to follow to implement the above approach.

  • Sort the array in ascending order using any sorting algorithm or any built-in sort function if your programming language supports it.
  • Then directly return the kth element from the starting of the array as you have sorted the array in ascending order.

Code Implementation
In this section, we will implement the code in various languages.

#include <stdio.h>
#include <stdlib.h>

int cmpfunc(const void* a, const void* b)
{
    return (*(int*)a - *(int*)b);
}

int kthSmallestelem(int arr[], int N, int K)
{
    qsort(arr, N, sizeof(int), cmpfunc);

    return arr[K - 1];
}

int main()
{
    int arr[] = { 121, 13, 45, 17, 19 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 2;

    printf("K'th smallest element is %d",
        kthSmallestelem(arr, N, K));
    return 0;
}



#include <bits/stdc++.h>
using namespace std;

int kthSmallestelem(int arr[], int N, int K)
{
    sort(arr, arr + N);

    return arr[K - 1];
}

int main()
{
    int arr[] = { 121, 13, 45, 17, 19 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 2;

    cout << "K'th smallest element is "
        << kthSmallestelem(arr, N, K);
    return 0;
}


import java.util.Arrays;
import java.util.Collections;

class PrepBytes {
    public static int kthSmallestelem(Integer[] arr, int K)
    {
        Arrays.sort(arr);

        return arr[K - 1];
    }

    public static void main(String[] args)
    {
        Integer arr[] = new Integer[] { 121, 13, 45, 17, 19 };
        int K = 2;

        System.out.print("K'th smallest element is "
                        + kthSmallestelem(arr, K));
    }
}

def kthSmallestelem(arr, N, K):

    arr.sort()
    return arr[K-1]


if __name__ == '__main__':
    arr = [ 121, 13, 45, 17, 19 ]
    N = len(arr)
    K = 2

    print("K'th smallest element is",
        kthSmallestelem(arr, N, K))

Output

K'th smallest element is 17

Explanation of the above code
We have followed a similar approach in all of the codes given above no matter of the language we have passed the array, its size, and the k to the fucntionKthSmallestelem which will first sort the array and then return the corresponding answer i.e, kth smallest element in an array.

Time Complexity
The time complexity of this approach will be O(nlogn) as we are sorting the array and the sorting of the array will take O(nlogn) for best algorithms.

Space Complexity
The auxiliary space complexity for this approach will be O(1) as we are not using any additional space.

Approach 2: Using Min Heap

Here we will see the solution approach using min heap and find the kth smallest element in an array. So the approach is very simple in this we just have to put all the elements in the min heap and after that, we have to get the min element from the heap k times.

Algorithm
The algorithm contains three steps.

  • Insert all the elements of the array in the min heap.
  • Now call the extractMin() function k times.
  • Now return the last value given by the extractMin() function.

Code Implementation
In this section, we will implement the code in various languages.

#include <climits>
#include <iostream>
using namespace std;

void swap(int* x, int* y);

class MinHeap {

    int* harr; 
    int capacity; 
    int heap_size; 
public:
    MinHeap(int a[], int size); 

    
    void MinHeapify(int i);
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }

    int extractMin(); 
    int getMin() { return harr[0]; } 
};

MinHeap::MinHeap(int a[], int size)
{
    heap_size = size;
    harr = a; 
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        MinHeapify(i);
        i--;
    }
}
int MinHeap::extractMin()
{
    if (heap_size == 0)
        return INT_MAX;

    
    int root = harr[0];


    if (heap_size > 1) {
        harr[0] = harr[heap_size - 1];
        MinHeapify(0);
    }
    heap_size--;

    return root;
}
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;

    if (l < heap_size && harr[l] < harr[i])
        smallest = l;

    if (r < heap_size && harr[r] < harr[smallest])
        smallest = r;

    if (smallest != i) {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}
int kthSmallest(int arr[], int N, int K)
{
    MinHeap mh(arr, N);

    for (int i = 0; i < K - 1; i++)
        mh.extractMin();

    return mh.getMin();
}

int main()
{
    int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 4;

    cout << "K'th smallest element is "
        << kthSmallest(arr, N, K);
    return 0;
}

import java.util.*;
 class PrepBytes {

    class MinHeap {
        int[] harr; 
        int capacity;
        int heap_size; 

        int parent(int i) { return (i - 1) / 2; }
        int left(int i) { return ((2 * i) + 1); }
        int right(int i) { return ((2 * i) + 2); }
        int getMin() { return harr[0]; } // Returns minimum

        void replaceMax(int x)
        {
            this.harr[0] = x;
            minHeapify(0);
        }
        MinHeap(int a[], int size)
        {
            heap_size = size;
            harr = a; 
            int i = (heap_size - 1) / 2;
            while (i >= 0) {
                minHeapify(i);
                i--;
            }
        }

        int extractMin()
        {
            if (heap_size == 0)
                return Integer.MAX_VALUE;

            int root = harr[0];

            
            if (heap_size > 1) {
                harr[0] = harr[heap_size - 1];
                minHeapify(0);
            }
            heap_size--;
            return root;
        }


        void minHeapify(int i)
        {
            int l = left(i);
            int r = right(i);
            int smallest = i;
            if (l < heap_size && harr[l] < harr[i])
                smallest = l;
            if (r < heap_size && harr[r] < harr[smallest])
                smallest = r;
            if (smallest != i) {
                int t = harr[i];
                harr[i] = harr[smallest];
                harr[smallest] = t;
                minHeapify(smallest);
            }
        }
    };

    int kthSmallest(int arr[], int N, int K)
    {

        MinHeap mh = new MinHeap(arr, N);


        for (int i = 0; i < K - 1; i++)
            mh.extractMin();

        return mh.getMin();
    }

    public static void main(String[] args)
    {
        int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
        int N = arr.length, K = 2;
        PrepBytes Prep = new PrepBytes();

        System.out.print("K'th smallest element is "
                        + Prep.kthSmallest(arr, N, K));
    }
}

class MinHeap:

    def __init__(self, a, size):

        self.harr = a

        self.capacity = None

        self.heap_size = size

        i = int((self.heap_size - 1) / 2)
        while i >= 0:
            self.minHeapify(i)
            i -= 1

    def parent(self, i):
        return (i - 1) / 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def getMin(self):
        return self.harr[0]

    def extractMin(self):
        if self.heap_size == 0:
            return float("inf")

        root = self.harr[0]

        if self.heap_size > 1:
            self.harr[0] = self.harr[self.heap_size - 1]
            self.minHeapify(0)
        self.heap_size -= 1
        return root

    def minHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        smallest = i
        if ((l < self.heap_size) and
                (self.harr[l] < self.harr[i])):
            smallest = l
        if ((r < self.heap_size) and
                (self.harr[r] < self.harr[smallest])):
            smallest = r
        if smallest != i:
            self.harr[i], self.harr[smallest] = (
                self.harr[smallest], self.harr[i])
            self.minHeapify(smallest)

def kthSmallest(arr, N, K):

    mh = MinHeap(arr, N)

    for i in range(K - 1):
        mh.extractMin()

    return mh.getMin()


if __name__ == '__main__':
    arr = [ 42, 49, 12, 11, 73, 85, 39 ]
    N = len(arr)
    K = 4

    print("K'th smallest element is", kthSmallest(arr, N, K))

Output

K'th smallest element is 42

Explanation of the above code
In all the code above we have followed the approach of min heap where we have put all the elements in min heap and after getting the minimum element k times we get our kth smallest element in an array.

Time Complexity
The time complexity of the above approach will be O(N+KlogN) where N is the size of the array and KlogN will be for the min heap as the elements are stored in sorted order.

Space Complexity
The space complexity of the above approach will be O(N) as we are storing all the elements of the array in the heap.

Approach 3: Using MaxHeap

By using the approach of max heap we can find the kth smallest element as here we have to put the first k elements in the max heap after that we have to compare the remaining elements with the root of the max heap if the root value is greater than the current element value then we will remove the root from the max heap and insert the current element.

Algorithm
The algorithm consists of some steps that we need to follow while working with the max heap approach to finding the kth smallest element in an array.

  • Build a max heap and insert the first k elements of the array in that max heap.
  • For the remaining element compare each of them with the root of the max heap.
  • If the value of the root of max heap is greater than the current element then remove the root of maxheap.
  • Now after all the complete iterations of the array, we will have the root element of the max heap as the kth smallest element.

Code Implementation
In this section, we will see the code implementation of the above approach in various programming languages.

// C++ program to find k'th smallest element using max heap

#include <bits/stdc++.h>
using namespace std;
void swap(int* x, int* y);

class MaxHeap {

    int* harr; 
    int capacity; 
    int heap_size; 

public:
    MaxHeap(int a[], int size); 
    void maxHeapify(
        int i); 
    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return (2 * i + 1); }
    int right(int i) { return (2 * i + 2); }

    int extractMax();
    int getMax() { return harr[0]; }

    void replaceMax(int x)
    {
        harr[0] = x;
        maxHeapify(0);
    }
};

MaxHeap::MaxHeap(int a[], int size)
{
    heap_size = size;
    harr = a; // store address of array
    int i = (heap_size - 1) / 2;
    while (i >= 0) {
        maxHeapify(i);
        i--;
    }
}

int MaxHeap::extractMax()
{
    if (heap_size == 0)
        return INT_MAX;

    int root = harr[0];

    if (heap_size > 1) {
        harr[0] = harr[heap_size - 1];
        maxHeapify(0);
    }
    heap_size--;

    return root;
}


void MaxHeap::maxHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int largest = i;

    if (l < heap_size && harr[l] > harr[i])
        largest = l;

    if (r < heap_size && harr[r] > harr[largest])
        largest = r;

    if (largest != i) {
        swap(&harr[i], &harr[largest]);
        maxHeapify(largest);
    }
}

void swap(int* x, int* y)
{
    int temp = *x;
    *x = *y;
    *y = temp;
}

int kthSmallestelem(int arr[], int N, int K)
{
    MaxHeap mh(arr, K);

    
    for (int i = K; i < N; i++)
        if (arr[i] < mh.getMax())
            mh.replaceMax(arr[i]);

    return mh.getMax();
}

int main()
{
    int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 3;

    cout << "K'th smallest element is "
        << kthSmallestelem(arr, N, K);
    return 0;
}

import java.util.*;
class PrepBytes {


    class MaxHeap {
        int[] harr; 
        int capacity; 
        int heap_size; 
                    

        int parent(int i) { return (i - 1) / 2; }
        int left(int i) { return (2 * i + 1); }
        int right(int i) { return (2 * i + 2); }
        int getMax() { return harr[0]; } 

        void replaceMax(int x)
        {
            this.harr[0] = x;
            maxHeapify(0);
        }
        MaxHeap(int a[], int size)
        {
            heap_size = size;
            harr = a;
            int i = (heap_size - 1) / 2;
            while (i >= 0) {
                maxHeapify(i);
                i--;
            }
        }

    
        int extractMax()
        {
            if (heap_size == 0)
                return Integer.MAX_VALUE;

            int root = harr[0];

    
            if (heap_size > 1) {
                harr[0] = harr[heap_size - 1];
                maxHeapify(0);
            }
            heap_size--;
            return root;
        }

        void maxHeapify(int i)
        {
            int l = left(i);
            int r = right(i);
            int largest = i;
            if (l < heap_size && harr[l] > harr[i])
                largest = l;
            if (r < heap_size && harr[r] > harr[largest])
                largest = r;
            if (largest != i) {
                int t = harr[i];
                harr[i] = harr[largest];
                harr[largest] = t;
                maxHeapify(largest);
            }
        }
    };

    
    int kthSmallestelem(int arr[], int N, int K)
    {

        MaxHeap mh = new MaxHeap(arr, K);

        for (int i = K; i < N; i++)
            if (arr[i] < mh.getMax())
                mh.replaceMax(arr[i]);

        return mh.getMax();
    }

    public static void main(String[] args)
    {
        int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
        int N = arr.length, K = 3;
        PrepBytes Prep = new PrepBytes();

        System.out.print("K'th smallest element is "
                        + Prep.kthSmallestelem(arr, N, K));
    }
}
class MaxHeap:
    def __init__(self, a, size):
        self.harr = a
        self.capacity = None
        self.heap_size = size

        i = int((self.heap_size - 1) / 2)
        while i >= 0:
            self.maxHeapify(i)
            i -= 1

    def parent(self, i):
        return (i - 1) / 2

    def left(self, i):
        return 2 * i + 1

    def right(self, i):
        return 2 * i + 2

    def getMax(self):
        return self.harr[0]

    def replaceMax(self, x):
        self.harr[0] = x
        self.maxHeapify(0)

    
    def extractMin(self):
        if self.heap_size == 0:
            return float("inf")

        # Store the maximum value.
        root = self.harr[0]

    
        if self.heap_size > 1:
            self.harr[0] = self.harr[self.heap_size - 1]
            self.maxHeapify(0)
        self.heap_size -= 1
        return root

    def maxHeapify(self, i):
        l = self.left(i)
        r = self.right(i)
        largest = i

        if ((l < self.heap_size) and
                (self.harr[l] > self.harr[i])):
            largest = l

        if ((r < self.heap_size) and
                (self.harr[r] > self.harr[largest])):
            largest = r

        if largest != i:
            self.harr[i], self.harr[largest] = (
                self.harr[largest], self.harr[i])
            self.maxHeapify(largest)

def kthSmallestelem(arr, N, K):
    mh = MaxHeap(arr, K)

    for i in range(K, N):
        if arr[i] < mh.getMax():
            mh.replaceMax(arr[i])

    return mh.getMax()


if __name__ == '__main__':
    arr = [42, 49, 12, 11, 73, 85, 39]
    N = len(arr)
    K = 3

    print("K'th smallest element is", kthSmallestelem(arr, N, K))

Output

K'th smallest element is 39

Explanation of the above code
In the above code we are using the max heap and implementing the max heap from the scratch after that we are calling the kthSmallestelem function which will give the result by following the approach and algorithm explained above.

Time Complexity
The time complexity of the above approach will be O(K+ (N-K)*LogK) because first we will insert the k elements in the max heap after that in the worst case we have to change the root element for the rest N-K times.

Space Complexity
The space complexity for the above approach will be O(K) because we are having only K elements in the max heap all the time.

Approach 4: Using Quick Select

This approach is similar to the first approach where we have used sorting, So suppose in the first approach we have used quick sort but instead of sorting the full array we have stopped in between then this will be quick select. In this approach, we will pick an element and move the element to its correct position and that element will partition the array and will check if that is not the kth element if yes then we will stop, and if not then we will not recur on both left and right parts we will recur on the corresponding part according to the position of the pivot.

Algorithm
Here we will discuss the algorithm of the above approach.

  • Apply the quick sort algorithm on the array.
  • Now move the pivot element to its correct position.
  • After that, we will check the index of the pivot element if the index is equal to k then we will stop.
  • Otherwise, if the index of the pivot element is less than k then we will recur for the right subarray else we will recur for the left subarray.
  • Will repeat this process until we have not found the kth smallest element in an array.

Code Implementation
Now we will see the code implementation in various languages.

#include <limits.h>
#include <stdio.h>

int partition(int arr[], int l, int r);

int kthSmallestelem(int arr[], int l, int r, int K)
{
    if (K > 0 && K <= r - l + 1) {

        int pos = partition(arr, l, r);

        if (pos - l == K - 1)
            return arr[pos];
        if (pos - l > K - 1) 
                        
            return kthSmallestelem(arr, l, pos - 1, K);

        return kthSmallestelem(arr, pos + 1, r,
                        K - pos + l - 1);
    }

    return INT_MAX;
}

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }

    swap(&arr[i], &arr[r]);
    return i;
}

int main()
{
    int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 4;
    printf("K'th smallest element is %d",
        kthSmallestelem(arr, 0, N - 1, K));
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
int partition(int arr[], int l, int r);
int kthSmallestelem(int arr[], int l, int r, int K)
{
    if (K > 0 && K <= r - l + 1) {

        int pos = partition(arr, l, r);

        if (pos - l == K - 1)
            return arr[pos];
        if (pos - l > K - 1) 
            return kthSmallestelem(arr, l, pos - 1, K);

        return kthSmallestelem(arr, pos + 1, r,
                        K - pos + l - 1);
    }

    return INT_MAX;
}

void swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int l, int r)
{
    int x = arr[r], i = l;
    for (int j = l; j <= r - 1; j++) {
        if (arr[j] <= x) {
            swap(&arr[i], &arr[j]);
            i++;
        }
    }

    swap(&arr[i], &arr[r]);
    return i;
}
int main()
{
    int arr[] = { 42, 49, 12, 11, 73, 85, 39 };
    int N = sizeof(arr) / sizeof(arr[0]), K = 4;
    cout << "K'th smallest element is "
        << kthSmallestelem(arr, 0, N - 1, K);
    return 0;
}

import java.util.Arrays;
import java.util.Collections;

class PrepBytes {

    public static int partition(Integer[] arr, int l, int r)
    {
        int x = arr[r], i = l;
        for (int j = l; j <= r - 1; j++) {
            if (arr[j] <= x) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

                i++;
            }
        }

        int temp = arr[i];
        arr[i] = arr[r];
        arr[r] = temp;

        return i;
    }

    public static int kthSmallestelem(Integer[] arr, int l,
                                int r, int K)
    {
        if (K > 0 && K <= r - l + 1) {

            int pos = partition(arr, l, r);

            if (pos - l == K - 1)
                return arr[pos];

            if (pos - l > K - 1)
                return kthSmallestelem(arr, l, pos - 1, K);

            return kthSmallestelem(arr, pos + 1, r,
                            K - pos + l - 1);
        }

        return Integer.MAX_VALUE;
    }

    public static void main(String[] args)
    {
        Integer arr[]
            = new Integer[] { 42, 49, 12, 11, 73, 85, 39 };;
        int K = 4;

        System.out.print(
            "K'th smallest element is "
            + kthSmallestelem(arr, 0, arr.length - 1, K));
    }
}

import sys


def kthSmallestelem(arr, l, r, K):

    
    if (K > 0 and K <= r - l + 1):

    
        pos = partition(arr, l, r)

        if (pos - l == K - 1):
            return arr[pos]
        if (pos - l > K - 1): 
            return kthSmallestelem(arr, l, pos - 1, K)

        return kthSmallestelem(arr, pos + 1, r,
                        K - pos + l - 1)


    return sys.maxsize


def partition(arr, l, r):

    x = arr[r]
    i = l
    for j in range(l, r):
        if (arr[j] <= x):
            arr[i], arr[j] = arr[j], arr[i]
            i += 1
    arr[i], arr[r] = arr[r], arr[i]
    return i
if __name__ == "__main__":

    arr = [42, 49, 12, 11, 73, 85, 39]
    N = len(arr)
    K = 4
    print("K'th smallest element is",
        kthSmallestelem(arr, 0, N - 1, K))

Output

K'th smallest element is 42

Explanation of the above code
In the above code, we have explained the quick select approach where we are using the quicksort until we find the kth smallest element in an array but with slight modifications as we are recurring on the left and right subarray according to the position of the pivot element.

Time Complexity
The time complexity of the above method will be O(N^2) in the worst case and O(N) in the average case as in the worst case we have to perform the complete quicksort.

Space Complexity
The space complexity of the above approach will be O(1) as we are not usng any additional space.

Approach 5: Using Map and Frequency of Elements

This approach is a bit similar to counting sort and Quickselect but it is much easier to implement as we are using the ordered map in this case which will store the elements in ascending order so we will store all the elements of the array in the map and after that, we will travel in the map by adding the frequency of the elements and will move till the sum of frequency is less than k.

Algorithm
Now, we will look at the algorithm of the above approach.

  • Store the frequency of each element of the array in the map
  • Now travel in the map and start to sum the frequencies of the element encountered till now.
  • The point or element at which the sum of frequency is greater than equal to k.
  • Then return the corresponding element.

Code Implementation
Now, we will look at the code implementation of the above approach in various languages.

#include <bits/stdc++.h>
using namespace std;

int Kth_smallestelem(map<int, int> mp, int K)
{
    int freq = 0;
    for (auto it = mp.begin(); it != mp.end(); it++) {
        freq += (it->second); 

        if (freq >= K)  
        {
            return it->first;
        }
    }

    return -1;  
}

int main()
{
    int N = 7;
    int K = 2;
    vector<int> arr = { 42, 49, 12, 11, 73, 85, 39 };

    map<int, int> mp;
    for (int i = 0; i < N; i++) {
        mp[arr[i]] += 1; 
    }

    int ans = Kth_smallestelem(mp, K);
    cout << "The Kth smallest element is " << ans
        << endl;

    return 0;
}

// Java program for the above approach

import java.util.*;

class PrepBytes {
    static int Kth_smallestelem(TreeMap<Integer, Integer> mp,
                            int K)
    {
        int freq = 0;
        for (Map.Entry it : mp.entrySet()) {

            freq += (int)it.getValue();

            
            if (freq >= K) {
                return (int)it.getKey();
            }
        }

        return -1; 
    }

    public static void main(String[] args)
    {
        int N = 7;
        int K = 2;
        int[] arr = { 42, 49, 12, 11, 73, 85, 39 };
        TreeMap<Integer, Integer> mp = new TreeMap<>();

        for (int i = 0; i < N; i++) {

            mp.put(arr[i], mp.getOrDefault(arr[i], 0) + 1);
        }

        int ans = Kth_smallestelem(mp, K);

        System.out.println(
            "The Kth smallest element is " + ans);
    }
}

def Kth_smallestelem(mp, K):

    freq = 0
    for it in sorted(mp.keys()):
        freq += mp[it] 
        if freq >= K: 
            return it 
            
    return -1


if __name__ == "__main__":
    N = 7
    K = 2
    arr = [42, 49, 12, 11, 73, 85, 39 ]
    mp = {}
    for i in range(N):
        if arr[i] in mp: 
            mp[arr[i]] = mp[arr[i]] + 1 # frequency
        else:
            mp[arr[i]] = 1

    # Function call
    ans = Kth_smallestelem(mp, K)
    print("The ", K, "th smallest element is ", ans)

Output

The  Kth smallest element is  12

Explanation of the above code
In the above code, we have used the map, and after that, we have used the above approach to find the kth smallest element in an array using the summation of frequency.

Time Complexity
The time complexity of the above approach will be O(NlogN) as we are storing the elements in an ordered map.

Space Complexity
The space complexity of the above method is O(N) as we are storing all the elements in the map.

Approach 6: Using Priority Queue

Here we will insert the elements into the priority queue until the size of it is less than equal to k after that we will compare all the remaining elements with the top element of the priority queue if the remaining element is less than the top of priority queue then we will remove the top and insert the current element in the priority queue and after the traversal of the array the top element of the priority queue will be the kth smallest element in an array.

Algorithm
The algorithm for the above approach is straightforward as

  • We have to insert the first k elements in the priority queue.
  • After that we will check the top element of the priority queue and compare it with the remaining elements
  • If the current remaining element is less than the top element of the priority queue then we will remove the top element from the priority queue and insert the current element.
  • We will continue this process until we have not traversed the whole array.
  • Now the top element of the priority queue will be our kth smallest element in an array.

Dry Run for the above Approach
Here we will perform the dry run of the above algorithm by taking an example.

  1. We have a given array.

  1. Now we will insert the first k elements in the priority queue after that the priority queue will look like this:

  1. Now we will iterate on the remaining array, now we are in element 11 which is smaller than the top element of the priority queue i.e, 49 so we will remove 49 and add 11 to the priority queue.

  1. Now, we are on element 73 which is greater than the top element of the priority queue i.e, 42 so we will now do anything same with 85.

  1. Now element 39 is smaller than the top element of the priority queue i.e, 42 so we will remove 42 and insert 39.

  1. Now our array iteration is over and our priority queue is looking like this hence our answer is the top element of the priority queue i.e, 39.

Code Implementation
Now, we will see the implementation of the above approach in various programming languages.

#include <bits/stdc++.h>
using namespace std;

int kthSmallestelem(int arr[], int N, int K)
{

    priority_queue<int> pq;

    for (int i = 0; i < K; i++) {
        pq.push(arr[i]);
    }
    for (int i = K; i < N; i++) {

        if (arr[i] < pq.top()) {
            pq.pop();
            pq.push(arr[i]);
        }
    }

    return pq.top();
}

int main()
{
    int N = 7;
    int arr[N] = { 42, 49, 12, 11, 73, 85, 39 };
    int K = 3;

    cout << "Kth Smallest Element is: "
        << kthSmallestelem(arr, N, K);
}

import java.util.*;
class MinHeapComparator implements Comparator<Integer> {

    public int compare(Integer number1, Integer number2)
    {
        int value = number1.compareTo(number2);

        if (value > 0) {
            return -1;
        }
        else if (value < 0) {
            return 1;
        }
        else {
            return 0;
        }
    }
}
class GFG {

    static int kthSmallestelem(int[] v, int N, int K)
    {
    
        PriorityQueue<Integer> heap1
            = new PriorityQueue<Integer>(
                new MinHeapComparator());

        for (int i = 0; i < N; ++i) {

            heap1.add(v[i]);

            if (heap1.size() > K) {
                heap1.remove();
            }
        }

        return heap1.peek();
    }

    public static void main(String[] args)
    {
        int[] vec
            = { 42, 49, 12, 11, 73, 85, 39 };

        int N = vec.length;

        int K = 3;

        System.out.println("Kth Smallest Element: "
                        + kthSmallestelem(vec, N, K));
    }
}

import heapq



def kthSmallest(arr, N, K):

    pq = []
    for i in range(K):

        heapq.heappush(pq, arr[i])
        heapq._heapify_max(pq)

    for i in range(K, N):

        
        if arr[i] < pq[0]:
            heapq.heappop(pq)

            # Push curr element
            heapq.heappush(pq, arr[i])
            heapq._heapify_max(pq)
    return pq[0]


if __name__ == "__main__":
    N = 7
    arr = [42, 49, 12, 11, 73, 85, 39 ]
    K = 3

    print("Kth Smallest Element is:", kthSmallest(arr, N, K))

Output

Kth Smallest Element is: 39

Explanation of the above code
In the above code, we have used the priority queue to find the kth smallest element in an array by following the algorithm explained above.

Time Complexity
The time complexity of the above code is O(K log K + (N – K) log K) as we are using a priority queue.

Space Complexity
The space complexity of the above code is O(K) as we are storing K elements in the priority queue.

Conclusion
Arrays are one of the most used data structures in any programming language and above we have discussed one of the asked questions from the array topic, i.e, find the kth smallest element in an array, we have discussed numerous approaches of the above problem and with them, we have also discussed the algorithm and code implementation with output and explanation of the same.

Frequently Asked Questions

1. Explain list vs array in programming languages.
An array is a data structure that stores a collection of elements, each identified by an index or a key. A list is a data structure that stores an ordered collection of elements.

2. What is the time complexity of finding the Kth smallest element in an array?
The time complexity of finding the Kth smallest element in an array depends on the algorithm used. Quickselect has an average time complexity of O(n), while heap sort has a time complexity of O(nlogn). Binary search has a time complexity of O(logn).

3. Can the Kth smallest element in an array be found in a sorted array?
Yes, the Kth smallest element in a sorted array can be found simply by selecting the Kth element in the array.

4. What is the difference between the Kth largest and Kth smallest element in an array?
The Kth largest element in an array is the element that would be at the (n-k+1)th position if the array were sorted in descending order, where n is the number of elements in the array. The Kth smallest element in an array, on the other hand, is the element that would be at the Kth position if the array were sorted in ascending order.

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Related Post