324. Wiggle Sort II – Leetcode Solutions

Example 1:

Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.

Example 2:

Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]

class Solution:
    def wiggleSort(self, nums: List[int]) -> None:
        """
        Reorders the array such that nums[0] < nums[1] > nums[2] < nums[3]...
        The function modifies the list in place and does not return anything.
        """
        # Step 1: Sort the array
        sorted_nums = sorted(nums)
        
        # Step 2: Find the middle index
        n = len(nums)
        
        # Step 3: Fill the even indices (0, 2, 4, ...) with the smaller half of the array
        # Fill the odd indices (1, 3, 5, ...) with the larger half of the array
        
        # Use reverse indexing to fill from the back of the sorted array
        # to ensure the correct alternation of large and small numbers
        mid = (n + 1) // 2
        
        # Step 4: Place the smaller half of sorted_nums into even indices
        nums[::2] = sorted_nums[:mid][::-1]
        
        # Step 5: Place the larger half of sorted_nums into odd indices
        nums[1::2] = sorted_nums[mid:][::-1]

class Solution {
public:
    void wiggleSort(std::vector<int>& nums) {
        // Step 1: Sort the array in ascending order
        std::sort(nums.begin(), nums.end());
        
        // Step 2: Create a copy of the sorted array
        std::vector<int> sorted(nums);
        
        int n = nums.size();
        int mid = (n - 1) / 2;  // Middle index for the "smaller" half
        int end = n - 1;        // Last index for the "larger" half

        // Step 3: Reorder the array by placing the smaller elements in the odd indices
        // and the larger elements in the even indices.
        for (int i = 0; i < n; ++i) {
            if (i % 2 == 0) {
                // Place smaller half elements at even indices
                nums[i] = sorted[mid--];
            } else {
                // Place larger half elements at odd indices
                nums[i] = sorted[end--];
            }
        }
    }
};

var wiggleSort = function(nums) {
    // First, we need to sort the array in non-decreasing order
    nums.sort((a, b) => a - b);

    // We will create a copy of the sorted array
    let sorted = nums.slice();

    // Find the middle index (we divide by 2 and round up for odd length arrays)
    let mid = Math.floor((nums.length + 1) / 2);

    // Now, we'll place elements into their correct positions
    // Fill elements in "wiggle" order: 
    // The even indexed elements will come from the smaller half
    // The odd indexed elements will come from the larger half

    let j = mid - 1; // This will be for the smaller half (elements 0 to mid-1)
    let k = nums.length - 1; // This will be for the larger half (elements mid to end)

    // Now we iterate through each index and place elements alternately
    for (let i = 0; i < nums.length; i++) {
        if (i % 2 === 0) {
            // For even index, pick element from the smaller half
            nums[i] = sorted[j];
            j--;
        } else {
            // For odd index, pick element from the larger half
            nums[i] = sorted[k];
            k--;
        }
    }
};

class Solution {
    public void wiggleSort(int[] nums) {
        // Step 1: Sort the array
        Arrays.sort(nums);
        
        // Create a temporary array to hold the result
        int[] result = new int[nums.length];
        
        // Step 2: Split the sorted array into two parts.
        // We need to place the smaller half of the sorted array at odd indices 
        // and the larger half at even indices, reversed.

        // Find the middle index (we divide the array into two parts)
        int n = nums.length;
        int mid = (n + 1) / 2;  // Length of the smaller half

        // Step 3: Fill the array from the end for both halves (right-to-left)
        // This helps in handling duplicate numbers.

        // j starts from the last element in the smaller half.
        // i starts from the last element in the larger half.
        int j = mid - 1;   // Index for the smaller half
        int i = n - 1;     // Index for the larger half

        // Step 4: Place the elements in a wiggle manner
        for (int k = 0; k < n; k++) {
            // If the index k is even, place an element from the smaller half
            if (k % 2 == 0) {
                result[k] = nums[j--];
            } else {
                // If the index k is odd, place an element from the larger half
                result[k] = nums[i--];
            }
        }

        // Step 5: Copy the result back to the original array
        System.arraycopy(result, 0, nums, 0, n);
    }
}