I implemented two solutions, both are common, using max-heap and quickselect. As usual I always used the last element of the array as pivot for quick partition, since I have no a priori knowledge on the distribution of inputs so I didn't bother. Both run similarly at 400 ms, horrible speed of coz. Then I chose to randomized the quick selection and this time the running speed is around 10 ms. So it appears that most of the test cases are heavily biased that they are mostly sorted using increasing order. Maybe it was designed on purpose, I don't know. But in case you ran into a similar performance issue, try to choose your pivots smartly. In fact it is always a good idea to randomize your quick select, I was just being lazy and thought the test cases are "random" enough themselves.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.