This is an interesting question I have found on the web. Given an array containing n numbers (with no information about them), we should pre-process the array in linear time so that we can return the k smallest elements in O(k) time, when we are given a number 1 <= k <= n
I have been discussing this problem with some friends but no one could find a solution; any help would be appreciated!
quick notes: -the order of the k smallest elements is not important -the elements in the array are number , might be integers and might be not (so no radix sort) -the number k is not know in the pre-processing stage.the preprocessing is O(n) time. the function ( find k smallest elements) on O(k) time .