324. Wiggle Sort II

Description

The task is to reorder an unsorted array nums such that nums[0] < nums[1] > nums[2] < nums[3]... (this is known as wiggle sort). This means that the elements at even indices should be less than their neighboring odd indices, and elements at odd indices should be greater than their neighbors.

Intuition

By sorting the array, we can easily place smaller numbers in the even positions and larger numbers in the odd positions. This ensures that the wiggle property is satisfied: numbers at odd positions are greater than their neighbors and numbers at even positions are smaller. The key is to rearrange the array by alternating between the two halves of the sorted array.

Approach

1. Sort the Array: First, sort the array to arrange the elements in increasing order.
2. Partition the Array: Calculate the middle index to divide the array into two halves: - Left half for the even indices (smaller numbers). - Right half for the odd indices (larger numbers).
3. Rearrange: Start filling the nums array by alternately taking elements from the left and right halves of the sorted array.
4. Final Structure: Place the smaller numbers from the left half of the sorted array in the even indices and the larger numbers from the right half in the odd indices.

Complexity

Time Complexity:

• Sorting the array takes (O(n \log n)), where n is the number of elements.
• Rearranging the elements takes (O(n)).
• Hence, the overall time complexity is (O(n \log n)).

Space Complexity:

• We use an additional array to store the sorted version of nums, which takes (O(n)) space.
• Therefore, the space complexity is (O(n)).

Code

C++

class Solution {
public:
    void wiggleSort(std::vector& nums) {
        std::vector sorted(nums);
        std::sort(sorted.begin(), sorted.end());

        int mid = (nums.size() + 1) / 2;
        int j = mid - 1;
        int k = nums.size() - 1;

        for (int i = 0; i < nums.size(); i++) {
            if (i % 2 == 0) {
                nums[i] = sorted[j--];
            } else {
                nums[i] = sorted[k--];
            }
        }
    }
};

Python

class Solution:
    def wiggleSort(self, nums):
        sorted_nums = sorted(nums)
        mid = (len(nums) + 1) // 2
        j, k = mid - 1, len(nums) - 1
        
        for i in range(len(nums)):
            if i % 2 == 0:
                nums[i] = sorted_nums[j]
                j -= 1
            else:
                nums[i] = sorted_nums[k]
                k -= 1

Java

class Solution {
    public void wiggleSort(int[] nums) {
        int[] sorted = nums.clone();
        Arrays.sort(sorted);

        int mid = (nums.length + 1) / 2;
        int j = mid - 1;
        int k = nums.length - 1;

        for (int i = 0; i < nums.length; i++) {
            if (i % 2 == 0) {
                nums[i] = sorted[j--];
            } else {
                nums[i] = sorted[k--];
            }
        }
    }
}

JavaScript

var wiggleSort = function (nums) {
    nums.sort((a, b) => a - b);

    let sorted = nums.slice();
    let mid = Math.floor((nums.length + 1) / 2);

    let j = mid - 1;
    let k = nums.length - 1;

    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            nums[i] = sorted[j--];
        } else {
            nums[i] = sorted[k--];
        }
    }
};