Arrays: Program to find the kth smallest element in the array

To find the kth smallest element from a given array, we will use a data structure called heap - specifically max heap.
To understand more about heap data structure, refer the heap section.
We will create a max heap which will only contain the top k smallest element and at the top of the heap,
it will contain the largest element among the k elements in the heap
 

How does it work?

We push the elements in the heap if the heap size is less than k or the top element value of the heap is greater
than the current element value. And doing so we will be left with the top k smallest elements in the heap
as we are popping the max elements from the heap if the size exceeds k

Algorithm

1. Create a max heap named maxHeap
2. For num in nums do:
   • If (size of maxHeap < k) OR (num < top element of maxHeap): add num to maxHeap
   • If the size of maxHeap > k: remove the top element from the maxHeap
3. Return the top element of the maxHeap

Complexity

Time Complexity: O(N * LogK)
Space Complexity: O(K)

The Time Complexity is O(N * LogK) as we are looping through every element of the array and pushing the element in the heap
which has a max size of k elements and takes O(LogK) to push the element in the heap. The Space Complexity is O(K) because
of the minHeap which contains at most k elements.

Java Code

import java.util.Comparator;
    import java.util.PriorityQueue;
    
    class KthSmallestElement{
    
        public static int getkthSmallestElement(int k, int nums[]) {
        
            // The reverseOrder function is used to make the heap max heap, by default it is min 
            //  heap
            PriorityQueue maxHeap = new PriorityQueue(Comparator.reverseOrder());
    
            for (int i = 0; i < nums.length; i++) {
    
                // Add the current num to the maxHeap if:
                // 1. Number of elements in the heap is less than k
                // 2. current num is less than the top of the heap
                if (maxHeap.size() < k || nums[i] < maxHeap.peek()) {
                    maxHeap.add(nums[i]);
                }
    
                // Keeping the size of maxHeap equal to k elements
                if (maxHeap.size() > k) {
                    maxHeap.poll();
                }
            }
    
            // Return the top elements, as it will be the kth smallest element
            return maxHeap.peek();
        }
    
        public static void main(String[] args) {
            int[] nums = { 8, 2, 6, 12, 11, 10, 35};
            int k = 4;
    
            System.out.println("The kth[" + k + "] smallest number in nums is: " + getkthSmallestElement(k, nums));
        }
    
  }

Output

The kth[4] smallest number in nums is: 10