values. Rearrange its elements so that they strictly alternate low and high:
values[0] < values[1] > values[2] < values[3] > values[4] < …
The input is guaranteed to have such an arrangement. If there are several, any of them is accepted. Return the rearranged array.
A sorting-based solution runs in O(n log n). Can you do it in O(n) time with O(1) extra space?values=[2, 2, 4, 1, 3, 3] → [2, 4, 2, 3, 1, 3]
For example [2, 4, 2, 3, 1, 3]: 2 < 4 > 2 < 3 > 1 < 3. Neighbours are never equal.
values=[6, 5, 5, 4] → [5, 6, 4, 5]
The two 5s cannot sit next to each other. One valid answer is [5, 6, 4, 5]: 5 < 6 > 4 < 5.
values=[9] → [9]
values=[2, 2, 4, 1, 3, 3]
[2, 4, 2, 3, 1, 3]
Run checks the first 3 tests in your browser. Submit checks all 35 tests on the server, hidden ones included.