CODEWITHSUNDEEP
arraysalgorithmsortingdata-structures
arctic_Oak
arctic_Oak

Reputation: 1024

Printing K smallest number in an array(not kth smallest)

I was giving an Interview.

INTERVIEWER: You have an array and you have to find k smallest element in that array and you have to be efficient as well?
EX: [2,1,4,5,0] and if input is 3 then output will be 0,1,2.

ME: I'll take k variables and iterate over each element of array and will store all different k smallest values in k different variables.

INTERVIEWER: What if you have millions of data and you have to find 10000 smallest variables?

ME: Yeah, taking 10000 variables is not practically possible. So, I'll iterate Bubble sort for 10,000 times over millions of data.

INTERVIEWER: No, okay next question!

So, I want to know what is the correct method for finding k smallest number in an array, specially when k is some very large number?

Upvotes: 0

Views: 634

Answers (2)

DAle
DAle

Reputation: 9117

First, we need to find the kth smallest element of the array. This can be done with any selection algorithm.

In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic.

Then we need to do a partition operation like in a quicksort algorithm. Partition reorders the array so that all elements with values less than the kth smallest element come before it, while all elements with values greater than the kth smallest element come after it. The complexity of the partition is O(n).

One pretty simple implementation of selection algorithm is a Quickselect algorithm (partition included), that is similar to Quicksort. The complexity of the algorithm is O(n) in the average case.

There are more sophisticated methods of finding the kth smallest element (kth order statistic) in O(n) in the worst case, for example Median of median algorithm. But I suppose Quickselect could be enough for an answer to the interview question.

Upvotes: 2

Lovlin Thakkar
Lovlin Thakkar

Reputation: 29

This can be solved using a MinHeap. MinHeap stores the nodes in a way that the parent node always has a value less than its child nodes. To extract the min value out of a MinHeap, one has to just extract the root's value.

Building a MinHeap from an array takes O(n) time complexity. (n being the number of values)

After extracting the root node, to find out the next min value, we have to replace it with the last value in the array representation of heap and minHeapify the Heap. Which takes O(logn) time complexity.

Say N is the number of values in the array and you are asked to find K smallest values. Then, by using this method, it would take O(N + K log(N)) time complexity. For example, if N is 106 and K is 103, it will take approximately 106 + 2*104 iterations, which roughly takes less than 1 second. Although the code is pretty complex to write.

Upvotes: 1

Related Questions