CODEWITHSUNDEEP
javaarrays
developer
developer

Reputation: 37

Optimization of Program to find kth smallest element in an array (Java, Expected time complexity O(n))

Q: Given an array arr[] and a number K where K is smaller than size of array, the task is to find the Kth smallest element in the given array. It is given that all array elements are distinct.

I have gone through all the post related to this question but none of them helped me with the time complexity issue. I am new to coding and am having a hard time optimizing my solutions.

Expected time complexity is O(n)

This is my function with time complexity O(nlogn):

public static void smallestk(int arr[],int k)
{
    Arrays.sort(arr);
    System.out.println(arr[k-1]);
}

The output is correct but I want to optimize my code from O(nlogn) to O(n)

Upvotes: 0

Views: 1061

Answers (1)

Sunder
Sunder

Reputation: 56

The best case to this problem is O(nlogk) and we can solve this using a max or min heap data structure. if k is small, this will be close to O(n). The idea is that we do not have to sort the entire array but to take a heap which is of the size k and always sort with in the k elements present in the heap.

  1. O(n) for iterating through the array

  2. O(logk) for sorting the k elements using Heap sort.

    public Integer getKthEle(Integer[] numbers, int k) {

    PriorityQueue<Integer> maxHeap = new PriorityQueue(k, new Comparator<Integer>() {

    public int compare(Integer a, Integer b) {
        return b-a;
    }

    }
);

for(int i=0;i<k;i++) {
    maxHeap.offer(numbers[i]);
}
// maintain the size k by adding to the queue if the next element is smaller than the head of the queue; remove from the head of the queue which is the largest element in the queue
for(int i=k;i<numbers.length;i++) {
    if(numbers[i] < maxHeap.peek()) {
        maxHeap.offer(numbers[i]);
        maxHeap.poll();
    } 
}


return maxHeap.peek();

    }

Upvotes: 1

Related Questions