We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Wiggle Sort II

Difficulty: Medium

Problem Description

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... You may assume the input array always has a valid answer.

Key Insights

  • The array needs to be rearranged in a specific wiggle pattern, alternating between less than and greater than comparisons.
  • Sorting the array can help us easily access elements for reordering.
  • The problem can be efficiently solved using a two-pointer technique after sorting the array.

Space and Time Complexity

Time Complexity: O(n log n) - due to sorting the array.
Space Complexity: O(n) - for the output array, though the problem can be solved in-place with O(1) extra space by reusing the input array.

Solution

To solve the problem, follow these steps:

  1. Sort the array. This allows easy access to the smallest and largest elements.
  2. Use two pointers to fill the output array in the required wiggle pattern. One pointer will start from the beginning of the sorted array, and the other from the middle to the end.
  3. Alternate filling the output array with elements from the two pointers, ensuring the wiggle condition is satisfied.

Code Solutions

def wiggleSort(nums):
    # Sort the original array
    nums.sort()
    n = len(nums)
    # Create a new array to hold the result
    result = [0] * n
    
    # Fill the odd indices with the larger half
    j = (n + 1) // 2  # Midpoint for the larger half
    for i in range(1, n, 2):
        result[i] = nums[j]
        j += 1
    
    # Fill the even indices with the smaller half
    j = 0  # Start from the beginning for the smaller half
    for i in range(0, n, 2):
        result[i] = nums[j]
        j += 1
    
    # Copy the result back to nums
    for i in range(n):
        nums[i] = result[i]
← Back to All Questions