The standard answer for this is to use max binary heap, which will provide you answer in O(nlogn) but I did not knew about that so I said I will start sorting the array using quick sort and will stop sorting when I find kth max, so no need to sort complete array and hence complexity is less than O(n) on average.