Wiggle Sort II

This optimal approach achieves O(N) time and O(1) space complexity, meeting the follow-up challenge. It avoids a full sort by finding the median element in linear time. Then, it uses a clever "virtual indexing" scheme to place elements correctly in-place. The idea is to partition the array into three groups: elements larger than the median, equal to the median, and smaller than the median. This partitioning is done on a "virtual" array that maps indices 0, 1, 2, ... to the desired wiggle positions 1, 3, 5, ..., 0, 2, 4, ....

• Find Median: Use an O(N) average time selection algorithm (like Quickselect) to find the median element of the array. The median is the (n+1)/2-th smallest element, which separates the array into a smaller half and a larger half.
• Virtual Indexing: Define a mapping function map(i) = (1 + 2*i) % (n | 1) where n is the array length. This function maps indices 0, 1, 2, ... to the desired wiggle positions 1, 3, 5, ..., 0, 2, 4, .... This places elements for the 'large' slots first, followed by elements for the 'small' slots.
• 3-Way Partition: Perform a 3-way partition (Dutch National Flag algorithm) on the array in-place. Instead of accessing elements by their direct index i, use the virtual index map(i). This partitions the array into three groups based on the median: elements larger than the median, elements equal to the median, and elements smaller than the median. The virtual indexing ensures they are placed into the correct final wiggle positions.

This advanced solution directly constructs the wiggle-sorted array without a full sort or an auxiliary array.

1. Median Finding: The first step is to find the value that partitions the numbers into two halves. This value is the median. We can find the k-th smallest element in an array in O(N) average time using the Quickselect algorithm. For this problem, we need the (n+1)/2-th smallest element.

2. Virtual Indexing and Partitioning: The core of the solution is to place all numbers larger than the median in the 'large' slots (odd indices) and all numbers smaller than the median in the 'small' slots (even indices). The numbers equal to the median will fill the remaining slots. This is achieved simultaneously using a single pass with the 3-way partition algorithm combined with virtual indexing. The mapping A(i) = (1 + 2*i) % (n | 1) ensures that as we iterate through i from 0 to n-1, we are considering positions in the order of odd_indices..., even_indices.... By partitioning based on this virtual layout, we move larger elements to the start of this virtual sequence (odd indices) and smaller elements to the end (even indices), achieving the wiggle sort in-place.

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        if (n <= 1) {
            return;
        }

        // Step 1: Find the median element. The median is the (n+1)/2-th smallest element.
        int median = findKthSmallest(nums, (n + 1) / 2);

        // Step 2: 3-way partition using virtual indexing.
        int left = 0, i = 0, right = n - 1;

        while (i <= right) {
            int mapped_i = mapIndex(i, n);
            if (nums[mapped_i] > median) {
                int mapped_left = mapIndex(left, n);
                swap(nums, mapped_i, mapped_left);
                left++;
                i++;
            } else if (nums[mapped_i] < median) {
                int mapped_right = mapIndex(right, n);
                swap(nums, mapped_i, mapped_right);
                right--;
            } else {
                i++;
            }
        }
    }

    // Maps an index i to its corresponding position in the wiggle-sorted array.
    private int mapIndex(int i, int n) {
        // n | 1 ensures the modulus is always odd, which is key to the mapping.
        return (1 + 2 * i) % (n | 1);
    }

    // Finds the k-th smallest element using Quickselect (O(N) average time).
    private int findKthSmallest(int[] nums, int k) {
        int[] temp = nums.clone(); // Use a copy to not disrupt the original array before partitioning
        int targetIndex = k - 1; // Convert 1-based k to 0-based index
        int left = 0, right = temp.length - 1;

        while (left <= right) {
            int pivotIndex = partition(temp, left, right);
            if (pivotIndex == targetIndex) {
                return temp[pivotIndex];
            } else if (pivotIndex < targetIndex) {
                left = pivotIndex + 1;
            } else {
                right = pivotIndex - 1;
            }
        }
        return -1; // Should not be reached
    }

    // Lomuto partition scheme for Quickselect.
    private int partition(int[] nums, int left, int right) {
        int pivotValue = nums[right];
        int storeIndex = left;
        for (int i = left; i < right; i++) {
            if (nums[i] < pivotValue) {
                swap(nums, storeIndex, i);
                storeIndex++;
            }
        }
        swap(nums, right, storeIndex);
        return storeIndex;
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}