As pointed out by jwangmcd in a comment, [4,5,5,6] is troublesome. Several (most?) solutions, including the judge's solution, don't solve it correctly. They leave [4,5,5,6], which is wrong. The only correct order is [5,6,4,5].
Edit: The judge's solution has been fixed and the test case included. Thanks, @1337c0d3r.
You're absolutely right! The problem should be changed to nums <= nums >= nums ..., or just stated that the elements in the array are distinct.
hi, @StefanPochmann, does it mean that we need to at least globally sort the array first with nlogn time? It does seem to be a local property, with O(n) time
@yanggao No, sorting isn't necessary, at least not fully. Partitioning around the median is enough, which can be done in O(n). I added some explanation / proof of my solution, where you can take the median for M and the smaller numbers (called S there) don't need to be in any particular order (and neither do the larger numbers, called L there).
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.