# [4,5,5,6] is wrong

• 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[0] <= nums[1] >= nums[2] ..., or just stated that the elements in the array are distinct.

• @phat2 Then it would be the same as the first version of the problem. No, it just needs to get fixed (and it will).

• Thanks Stefan! I've just fixed the judge's solution and added the test case.

• 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.