# 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

- Create a max heap named maxHeap
- 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

- 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