324. Wiggle Sort II

Wiggle Sort II is a very interesting question that took me a day to solve it.

A naive solution is to Sort it, then partition the lower half of the array to the odd indices of the array and upper half of the array to the even indices of the array.

However, doing so would give u O(nlogn) solution, but not O(n) solution as the question required.

The idea of solving it is to make use of 3-way quick select, to partition the array based on the median.

The idea of 3-way quick select:
Select a pivot, then partition the array according to the following rules:
1. the leftmost side of the array contains elements that are lesser than the pivot
2. the middle side of the array contains elements that equals to the pivot
3. the rightmost side of the array contains elements that are larger than the pivot

Do note that 3-way quick select does not guarantee O(n) time performance, but it gives O(n) average time performance. You can make it to be guarantee O(n) average time performance by randomizing the pivot, but I did not do so in the code.

After performing 3-way quick select and finding the median,
we need to map the array to the wiggle-sorted array format, the idea of doing this without any extra space is to make use of "virtual index" technique.

Note that
for an array which is partitioned by median, for example:
[4, 5, 5, 6]

we know that the desired output is:
[5, 6, 4, 5]

if we map the indices, they are: [0, 1, 2, 3] -> [1, 3, 0, 2]

we can see that
(0, 1) -> (2, 0)
(2, 3) -> (3, 1)

We can then formulate the mapping as:
if(i <= mid) return (mid-i)*2;
else return 1 + 2*(n - i - 1);

using this concept, we can run a loop based on the virtual index, and check if the number on virtual index is correct.

See: