Kth smallest element - GeeksforGeeks

The problem says that you are given an array of n size. The array is not sorted and your task is to find the kth smallest element in the array.

So you could have technically returned the element at arr[k-1] if the array was sorted, which means technically in a sorted array the element at the k-1 index would be the kth smallest element. You can use the prdefined sort method like Arrays.sort() to sort the array in ascending order and then just return arr[k-1] to get the answer.

class Solution{
    public static int kthSmallest(int[] arr, int l, int r, int k) 
    { 
        //Your code here
        Arrays.sort(arr);
        return arr[k-1];
    } 
}

This would give you the best time complexity but in case of an interview, the interviewer will not allow you to use sort functions, so that time you will have to use any sorting algorithm or think of any other way to optimize the problem.

Using Sorting algorithm

Let's see how we can achieve the answer by using sorting algorithm. If we use either merge sort or quick sort then we can get an average timecomplexity of O(nlogn) but there are are still certain factors that must be taken into consideration. for now I am showing you the merge sort code, but do keep in mind there are better solutions possible.

By applying quick sort:-

class Solution{
    public static int kthSmallest(int[] arr, int l, int r, int k) 
    { 
        //Your code here
        int[] ans=sort(arr);
        return ans[k-1];
    }
    //merge sort algorithm
    public static int[] sort(int[] arr){
        if(arr.length==1)
            return arr;
        int mid=arr.length/2;
        int[] left=sort(Arrays.copyOfRange(arr,0,mid));
        int[] right=sort(Arrays.copyOfRange(arr,mid,arr.length));
        return merge(left,right);
    }

    public static int[] merge(int[] a,int[] b){
        int i=0,j=0,k=0;
        int[] arr=new int[a.length + b.length];
        while(i<a.length && j<b.length){
            if(a[i]<b[j])
            arr[k++]=a[i++];
            else
            arr[k++]=b[j++];
        }
        while(i<a.length)
        arr[k++]=a[i++];
        while(j<b.length)
        arr[k++]=b[j++];
        return arr;
    }
}

I am not going to explain how merge sort or quick sort works in this blog. That's the topic of another blog. But in simple words rather than using the sort() function we are implementing our own method.

Using PriorityQueue

This is the best possible and the most optimized solution of the problem. Here we will be using a data structure PriorityQueue. This implements the minheap which is a heap data structure and when we pop an element from the minheap it gives the smallest element in the array, I'll highly suggest you to learn more about heap and PriorityQueue before trying this. Now lets talk about the algorithm, by now I hope you know that PriorityQueue implements minheap under the hood. Here we have created a PriorityQueue minheap and then we are inserting elements from the array to the minheap , and when the size of minheap exceeds k we compare the current element with the root of the minheap. If the current element is smaller, it means we have found a smaller element than the current kth smallest in the array. Therefore, we remove the root (largest element in the minheap) and insert the current element. This process ensures that the minheap always contains the k smallest elements encountered so far.

After processing all elements in the array, the root of the minheap will be the kth smallest element. Since we are using a min-heap, the root always represents the smallest element among the k elements stored in the minheap.

The time complexity of this approach is O(n log k), where n is the size of the array. This is because each insertion and removal operation on the minheap takes O(log k) time, and we perform these operations for each element in the array.

import java.util.PriorityQueue;

public class KthSmallestElement {

    public static int kthSmallest(int[] arr, int k) {
        // Create a min heap (priority queue)
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();

        // Iterate through the array
        for (int num : arr) {
            // Add the current element to the min heap
            minHeap.offer(num);

            // If the size of the min heap exceeds k, remove the smallest element
            if (minHeap.size() > k) {
                minHeap.poll();
            }
        }

        // The root of the min heap is the kth smallest element
        return minHeap.poll();
    }

    public static void main(String[] args) {
        int[] arr = {7, 10, 4, 3, 20, 15};
        int k = 4;

        int result = kthSmallest(arr, k);
        System.out.println("The " + k + "th smallest element is: " + result);
    }
}

Data structures and algorithms require a lots of practice, so make sure after fully understanding the problem and the solutions your do practice it multiple times. So those were the three ways how to find the kth smallest element in the array, hope you find it helpful and for more such content do follow Nerdbash blogs and you can also follow me on Youtube and facebook , there I upload content on similar topics. Till then goodbye, have a goodday and keep coding!