Leetcode 324. Wiggle Sort II

Explanation

In this problem, we are asked to rearrange an unsorted array in a way that every other element is less than or greater than its neighbors, meaning it should follow a pattern such as nums[0] < nums[1] > nums[2] < nums[3]....

This format is referred to as "wiggle sort". The challenge lies in finding the algorithm that can achieve this pattern in the most efficient way.

To solve the problem, we use the following steps:

1. Calculate the median of the array.
2. Use index-rewiring to assign the values from the two halves of the array to odd and even indices respectively.

Basically, the secret sauce here is to use a 'virtual' index method (index-rewiring). With the help of this method, the original array would be 'virtually' partitioned into two halves, small half and large half, where odd indices are mapped to the first half and even numbers are mapped to the second half.

In an example like this: nums = [1, 5, 1, 1, 6, 4], the median would be 1. We would then use the 'virtual' index to rewire the array, giving us [1, 4, 1, 5, 1, 6].

Solution

C++

1
2cpp
3class Solution {
4 public:
5  void wiggleSort(vector<int>& nums) {
6    const int n = nums.size();
7    const auto it = begin(nums) + n / 2;
8
9    // Calculates the median of the array.
10    nth_element(begin(nums), it, end(nums));
11    const int median = *it;
12
13    // Maps physical index to virtual index.
14    // (0, 1, 2, 3, 4, 5) -> (1, 3, 5, 0, 2, 4)
15    // This places the larger half of the array on odd indexes and
16    // the smaller half of the array on even indexes.
17#define A(i) nums[(1 + 2 * i) % (n | 1)]
18
19    // Reordering based on comparison with the median.
20    for (int i = 0, j = 0, k = n - 1; i <= k;)
21      if (A(i) > median)
22        swap(A(i++), A(j++));
23      else if (A(i) < median)
24        swap(A(i), A(k--));
25      else
26        ++i;
27  }
28};

We do not currently have code implementations for the other languages.### Python

Despite being a high-level language, Python too can be used to solve this problem efficiently. The Pythonic way of solving this problem would use most of Python's built-in methods and utilities.

1
2python
3def wiggleSort(nums):
4    nums.sort()
5    half = len(nums[::2])# half of the length
6    nums[::2], nums[1::2] = nums[:half][::-1], nums[half:][::-1]

In this Pythonic solution, we initially sort the array. After that, we first update the even index numbers to be the smaller half of the numbers in reverse. Then, we update the odd index numbers to be the remaining (larger) half of the numbers in reverse.

JavaScript

We can implement this using JavaScript as follows:

1
2javascript
3function wiggleSort(nums) {
4    const temp = Array.from(nums).sort((a, b) => a - b);
5    let mid = Math.floor((nums.length-1)/2);
6    let end = nums.length-1;
7    for (let i = 0; i < nums.length; i++) {
8        if(i%2 === 0) {
9            nums[i] = temp[mid--];
10        } else {
11            nums[i] = temp[end--];
12        }
13    }
14};

In JavaScript, we still maintain the sort-first approach. The difference is that in the alternating index, we set it to the middle number (for even indices) and the last number (for odd indices), then decrease the corresponding index.

Java

In Java, we can implement the Wiggle Sort problem using the same approach:

1
2java
3public class Solution {
4    public void wiggleSort(int[] nums) {
5        int[] copy = Arrays.copyOf(nums, nums.length);
6        Arrays.sort(copy);
7        int n = nums.length;
8        int mid = (n % 2 == 0) ? n/2-1 : n/2;
9        int index = 0;
10        for(int i=0; i<=mid; i++){
11            nums[index] = copy[mid-i];
12            if(index+1 < n)
13                nums[index+1] = copy[n-i-1];
14            index += 2;
15        }
16    }
17}

In Java, we have the Arrays.copyOf and Arrays.sort utility to help copy and sort the array respectively. Afterwards, we simply loop through the array setting the even indices to the corresponding value from the smaller half of the copy array, and odd indices to the corresponding value from the larger half of the copy array.