use MaxHeap data structure O(n) use heap sort O(klogn) total O(n+klogn)

Can be done in O(n) (found solution on the internet) a) First find the kth biggest no. which can be done in logn (variant of Quicksort) b) Scan the array for all number greater than or equal to kth biggest no. which is O(n)

int[] counts = new int[10000]; for (int i : nums) //O(n) counts[i]++; for (int i = 9999; i >= 0; i--){ //O(1) k = k - counts[i]; if (k <= 0) return i; } return 0;

As it was correctly noted in the first answer, you can find (n-k)th order statistic and then do a partition with it (like in quicksort). It will take O(n) time for (n-k)th statistic and O(n) for partition. The only problem I see is that I don't use the information about distribution of numbers.

build a sorted array of k elements from the first k elements of the array. from item k + 1 to the last item in the random array, if the item is greater than the smallest number in the sorted array, insert it into the sorted array.

// in C# using a little LINQ and iterator convenience // // GetKthBiggest(k) => O(n) overall since it is composed of O(3n): // O(n) to do CountingSort() // O(n) to enumerate all of the count buckets in GetBiggest() // O(n) to also enumerate the bucket counts and yield each one public class KthBiggest { IReadOnlyList values; int[] counts; public KthBiggest(IReadOnlyList a, int maxValue) { values = a; counts = new int[maxValue + 1]; CountSort(); } void CountSort() { foreach (int i in values) counts[i]++; // IndexOutOfRangeException if any value exceeds given maxValue } public IEnumerable NextBiggest() { for (int i = 0; i < counts.Length; ++i ) { if (counts[i] != 0) { int c = counts[i]; while (c-- != 0) yield return i; } } } public int GetKthBiggest(int k) { if (k < 1) { throw new InvalidOperationException(); } // First() will throw for us due to empty enumeration input if not enough values present return NextBiggest().Skip(k - 1).First(); } }

Can be done in O(n) (found solution on the internet) a) First find the kth biggest no. which can be done in logn (variant of Quicksort) b) Scan the array for all number greater than or equal to kth biggest no. which is O(n)