324. Wiggle Sort II

  • 25.4%

https://leetcode.com/problems/wiggle-sort-ii/?tab=Description

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]….

1
2
3
Example:
(1) Given nums = [1, 5, 1, 1, 6, 4], one possible answer is [1, 4, 1, 5, 1, 6].
(2) Given nums = [1, 3, 2, 2, 3, 1], one possible answer is [2, 3, 1, 3, 1, 2].

Note:

You may assume all input has valid answer.

Follow Up:

Can you do it in O(n) time and/or in-place with O(1) extra space?


https://discuss.leetcode.com/topic/32929/o-n-o-1-after-median-virtual-indexing

O(n)+O(1) after median — Virtual Indexing

This post is mainly about what I call “virtual indexing” technique (I’m sure I’m not the first who came up with this, but I couldn’t find anything about it, so I made up a name as well. If you know better, let me know).

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
void wiggleSort(vector<int>& nums) {
int n = nums.size();

// Find a median.
auto midptr = nums.begin() + n / 2;
nth_element(nums.begin(), midptr, nums.end());
int mid = *midptr;

// Index-rewiring.
#define A(i) nums[(1+2*(i)) % (n|1)]

// 3-way-partition-to-wiggly in O(n) time with O(1) space.
int i = 0, j = 0, k = n - 1;
while (j <= k) {
if (A(j) > mid)
swap(A(i++), A(j++));
else if (A(j) < mid)
swap(A(j), A(k--));
else
j++;
}
}

Explanation

First I find a median using nth_element. That only guarantees O(n) average time complexity and I don’t know about space complexity. I might write this myself using O(n) time and O(1) space, but that’s not what I want to show here.

This post is about what comes after that. We can use three-way partitioning to arrange the numbers so that those larger than the median come first, then those equal to the median come next, and then those smaller than the median come last.

Ordinarily, you’d then use one more phase to bring the numbers to their final positions to reach the overall wiggle-property. But I don’t know a nice O(1) space way for this. Instead, I embed this right into the partitioning algorithm. That algorithm simply works with indexes 0 to n-1 as usual, but sneaky as I am, I rewire those indexes where I want the numbers to actually end up. The partitioning-algorithm doesn’t even know that I’m doing that, it just works like normal (it just uses A(x) instead of nums[x]).

Let’s say nums is [10,11,…,19]. Then after nth_element and ordinary partitioning, we might have this (15 is my median):

1
2
index:     0  1  2  3   4   5  6  7  8  9
number: 18 17 19 16 15 11 14 10 13 12

I rewire it so that the first spot has index 5, the second spot has index 0, etc, so that I might get this instead:

1
2
index:     5  0  6  1  7  2  8  3  9  4
number: 11 18 14 17 10 19 13 16 12 15

And 11 18 14 17 10 19 13 16 12 15 is perfectly wiggly. And the whole partitioning-to-wiggly-arrangement (everything after finding the median) only takes O(n) time and O(1) space.

If the above description is unclear, maybe this explicit listing helps:

1
2
3
4
5
6
7
8
9
10
Accessing A(0) actually accesses nums[1].
Accessing A(1) actually accesses nums[3].
Accessing A(2) actually accesses nums[5].
Accessing A(3) actually accesses nums[7].
Accessing A(4) actually accesses nums[9].
Accessing A(5) actually accesses nums[0].
Accessing A(6) actually accesses nums[2].
Accessing A(7) actually accesses nums[4].
Accessing A(8) actually accesses nums[6].
Accessing A(9) actually accesses nums[8].

Props to apolloydy’s solution, I knew the partitioning algorithm already but I didn’t know the name. And apolloydy’s idea to partition to reverse order happened to make the index rewiring simpler.


https://discuss.leetcode.com/topic/41464/step-by-step-explanation-of-index-mapping-in-java

Step by step explanation of index mapping in Java

The virtual index idea in the post https://leetcode.com/discuss/77133/o-n-o-1-after-median-virtual-indexing
is very brilliant! However, it takes me a while to understand why and how it works. There is no ‘nth_element’ in Java, but you can use ‘findKthLargest’ function from “https://leetcode.com/problems/kth-largest-element-in-an-array/" to get the median element in average O(n) time and O(1) space.

Assume your original array is {6,13,5,4,5,2}. After you get median element, the ‘nums’ is partially sorted such that the first half is larger or equal to the median, the second half is smaller or equal to the median, i.e

1
2
3
13   6   5   5   4   2

M

In the post https://leetcode.com/discuss/76965/3-lines-python-with-explanation-proof, we have learned that , to get wiggle sort, you want to put the number in the following way such that

(1) elements smaller than the ‘median’ are put into the last even slots

(2) elements larger than the ‘median’ are put into the first odd slots

(3) the medians are put into the remaining slots.

1
2
3
Index :       0   1   2   3   4   5
Small half: M S S
Large half: L L M

M - Median, S-Small, L-Large. In this example, we want to put {13, 6, 5} in index 1,3,5 and {5,4,2} in index {0,2,4}

The index mapping, (1 + 2 * index) % (n | 1) combined with ‘Color sort’, will do the job.

After selecting the median element, which is 5 in this example, we continue as the following

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
Mapped_idx[Left] denotes the position where the next smaller-than median element  will be inserted.
Mapped_idx[Right] denotes the position where the next larger-than median element will be inserted.


Step 1:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[Mapped_idx[i]] = nums[1] = 6 > 5, so it is ok to put 6 in the first odd index 1.
We increment i and left.


Step 2:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[3] = 5 = 5, so it is ok to put 6 in the index 3. We increment i.


Step 3:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 4 2
Left
i
Right
nums[5] = 2 < 5, so we want to put it to the last even index 4 (pointed by Right).
So, we swap nums[Mapped_idx[i]] with nums[Mapped_idx[Right]], i.e. nums[5] with nums[4],
and decrement Right.




Step 4:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 5 5 2 4
Left
i
Right
nums[5] = 4 < 5, so we want to put it to the second last even index 2. So, we swap
nums[5] with nums[2], and decrement Right.




Step 5:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 4 5 2 5
Left
i
Right
nums[5] = 5 < 5, it is ok to put it there, we increment i.


Step 6:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 13 6 4 5 2 5
Left
i
Right
nums[0] = 13 > 5, so, we want to put it to the next odd index which is 3 (pointed by 'Left').
So, we swap nums[0] with nums[3], and increment 'Left' and 'i'.


Step Final:
Original idx: 0 1 2 3 4 5
Mapped idx: 1 3 5 0 2 4
Array: 5 6 4 13 2 5
Left
i
Right
i > Right, we get the final wiggle array 5 6 4 13 2 5 !

The code is the following:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public void wiggleSort(int[] nums) {
int median = findKthLargest(nums, (nums.length + 1) / 2);
int n = nums.length;

int left = 0, i = 0, right = n - 1;

while (i <= right) {

if (nums[newIndex(i,n)] > median) {
swap(nums, newIndex(left++,n), newIndex(i++,n));
}
else if (nums[newIndex(i,n)] < median) {
swap(nums, newIndex(right--,n), newIndex(i,n));
}
else {
i++;
}
}


}

private int newIndex(int index, int n) {
return (1 + 2*index) % (n | 1);
}

https://discuss.leetcode.com/topic/32861/3-lines-python-with-explanation-proof

3 lines Python, with Explanation / Proof

Solution

Roughly speaking I put the smaller half of the numbers on the even indexes and the larger half on the odd indexes.

1
2
3
4
def wiggleSort(self, nums):
nums.sort()
half = len(nums[::2])
nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]

Alternative, maybe nicer, maybe not:

1
2
3
4
def wiggleSort(self, nums):
nums.sort()
half = len(nums[::2]) - 1
nums[::2], nums[1::2] = nums[half::-1], nums[:half:-1]

Explanation / Proof

I put the smaller half of the numbers on the even indexes and the larger half on the odd indexes, both from right to left:

1
2
3
4
5
6
Example nums = [1,2,...,7]      Example nums = [1,2,...,8] 

Small half: 4 . 3 . 2 . 1 Small half: 4 . 3 . 2 . 1 .
Large half: . 7 . 6 . 5 . Large half: . 8 . 7 . 6 . 5
-------------------------- --------------------------
Together: 4 7 3 6 2 5 1 Together: 4 8 3 7 2 6 1 5

I want:

  • Odd-index numbers are larger than their neighbors.

Since I put the larger numbers on the odd indexes, clearly I already have:

  • Odd-index numbers are larger than or equal to their neighbors.

Could they be “equal to”? That would require some number M to appear both in the smaller and the larger half. It would be the largest in the smaller half and the smallest in the larger half. Examples again, where S means some number smaller than M and L means some number larger than M.

1
2
3
4
Small half:  M . S . S . S      Small half:  M . S . S . S .
Large half: . L . L . M . Large half: . L . L . L . M
-------------------------- --------------------------
Together: M L S L S M S Together: M L S L S L S M

You can see the two M are quite far apart. Of course M could appear more than just twice, for example:

1
2
3
4
Small half:  M . M . S . S      Small half:  M . S . S . S .
Large half: . L . L . M . Large half: . L . M . M . M
-------------------------- --------------------------
Together: M L M L S M S Together: M L S M S M S M

You can see that with seven numbers, three M are no problem. And with eight numbers, four M are no problem. Should be easy to see that in general, with n numbers, floor(n/2) times M is no problem. Now, if there were more M than that, then my method would fail. But… it would also be impossible:

  • If n is even, then having more than n/2 times the same number clearly is unsolvable, because you’d have to put two of them next to each other, no matter how you arrange them.
  • If n is odd, then the only way to successfully arrange a number appearing more than floor(n/2) times is if it appears exactly floor(n/2)+1 times and you put them on all the even indexes. And to have the wiggle-property, all the other numbers would have to be larger. But then we wouldn’t have an M in both the smaller and the larger half.

So if the input has a valid answer at all, then my code will find one.


https://discuss.leetcode.com/topic/32920/o-n-time-o-1-space-solution-with-detail-explanations

O(n)-time O(1)-space solution with detail explanations

Methodology:

Idea 1.

As @whnzinc pointed out in this thread, all elements in nums can be classified into three categories:

(1) Larger than the median;

(2) Equal to the median;

(3) Smaller than the median.

Note that it’s possible to find the median within O(n)-time and O(1)-space.

Note: We can use nth_element to find the median, but it’s not O(n)-time and O(1)-space. For the sake of simplicity, I might use nth_element as well.

Idea 2.

As @StefanPochmann pointed out in this thread, we can arrange the elements in the three categories in a deterministic way.

(1) Elements that are larger than the median: we can put them in the first few odd slots;

(2) Elements that are smaller than the median: we can put them in the last few even slots;

(3) Elements that equal the median: we can put them in the remaining slots.

Update: According to @StefanPochmann’s thread, we can use a one-pass three-way partition to rearrange all elements. His idea is to re-map the indices into its destined indices, odd indices first and even indices follow.

Example:

1
2
Original Indices:    0  1  2  3  4  5  6  7  8  9 10 11
Mapped Indices: 1 3 5 7 9 11 0 2 4 6 8 10

(its reverse mapping is)

1
2
Mapped Indices:      0  1  2  3  4  5  6  7  8  9 10 11
Original Indices: 6 0 7 1 8 2 9 3 10 4 11 5 (wiggled)

In order to achieve this, we can use a function alike

1
2
3
int map_index(int idx, int n) {
return (2 * idx + 1) % (n | 1);
}

where (n | 1) calculates the nearest odd that is not less than n.

Complexities: (On the condition that finding median is O(n)-time and O(1)-space)

  • Time: O(n)

  • Space: O(1)

C++ (Updated, 44ms):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
void wiggleSort(vector<int>& nums) {
if (nums.empty()) {
return;
}
int n = nums.size();

// Step 1: Find the median
vector<int>::iterator nth = next(nums.begin(), n / 2);
nth_element(nums.begin(), nth, nums.end());
int median = *nth;

// Step 2: Tripartie partition within O(n)-time & O(1)-space.
auto m = [n](int idx) { return (2 * idx + 1) % (n | 1); };
int first = 0, mid = 0, last = n - 1;
while (mid <= last) {
if (nums[m(mid)] > median) {
swap(nums[m(first)], nums[m(mid)]);
++first;
++mid;
}
else if (nums[m(mid)] < median) {
swap(nums[m(mid)], nums[m(last)]);
--last;
}
else {
++mid;
}
}
}
};

https://discuss.leetcode.com/topic/32882/short-simple-c

Short simple C++

1
2
3
4
5
6
void wiggleSort(vector<int>& nums) {
vector<int> sorted(nums);
sort(sorted.begin(), sorted.end());
for (int i=nums.size()-1, j=0, k=i/2+1; i>=0; i--)
nums[i] = sorted[i&1 ? k++ : j++];
}

Sort and then write the smaller half of the numbers on the even indexes and the larger half of the numbers on the odd indexes, both from the back. Example:

1
2
3
4
Small half:    4 . 3 . 2 . 1 . 0 .
Large half: . 9 . 8 . 7 . 6 . 5
----------------------------------
Together: 4 9 3 8 2 7 1 6 0 5

So write nums from the back, interweaving sorted[0..4] (indexed by j) and sorted[5..9] (indexed by k).

For more explanation/proof, see my equivalent Python solution.


https://discuss.leetcode.com/topic/32923/simple-modulo-solution

Simple modulo solution

Once again I sort and then spread the numbers like in this example with nums=[0,1,…,9]:

1
2
3
4
Small half:    4 . 3 . 2 . 1 . 0 .
Large half: . 9 . 8 . 7 . 6 . 5
----------------------------------
Together: 4 9 3 8 2 7 1 6 0 5

Just write the numbers 9, 8, 7, etc at indexes 1, 3, 5, etc. Use modulo to wrap around for the second round (the even indexes).

Python

1
2
3
def wiggleSort(self, nums):
for i, num in enumerate(sorted(nums)[::-1]):
nums[(1+2*i) % (len(nums)|1)] = num

C++

1
2
3
4
5
6
7
void wiggleSort(vector<int>& nums) {
vector<int> sorted(nums);
sort(sorted.rbegin(), sorted.rend());
int n = nums.size(), m = n | 1;
for (int i=0; i<n; i++)
nums[(1+2*i)%m] = sorted[i];
}

Or:

1
2
3
4
5
6
7
void wiggleSort(vector<int>& nums) {
vector<int> sorted(nums);
sort(sorted.rbegin(), sorted.rend());
int n = nums.size(), m = n | 1, i = -1;
for (int num : sorted)
nums[(i+=2)%m] = num;
}
谢谢你,可爱的朋友。