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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Wiggle Sort II

Number: 324

Difficulty: Medium

Paid? No

Companies: Amazon, Google

Problem Description

Given an integer array nums, rearrange it so that nums[0] < nums[1] > nums[2] < nums[3]... You can assume that a valid rearrangement exists for the input.

Key Insights

  • Finding the median helps partition the numbers into three groups: larger than, equal to, and less than the median.
  • Using virtual indexing (mapping the actual index to a new index) allows in-place rearrangement.
  • The three-way partitioning (Dutch National Flag algorithm) ensures that numbers larger than the median are in the odd indices and those smaller are in the even indices.
  • Although finding the median can be done in O(n) using quickselect, sorting and then selecting is often simpler though it results in O(n log n) time.

Space and Time Complexity

Time Complexity: O(n) average if using quickselect; O(n log n) if sorting is used. Space Complexity: O(1) extra space (in-place rearrangement) apart from the recursion stack in quickselect.

Solution

The solution consists of three key steps:

  1. Find the median of the array. This can be achieved in O(n) time using quickselect or in O(n log n) time by sorting.
  2. Create a virtual index mapping function that reorders the index positions. For an index i, the new index is computed as (1 + 2*i) % (n | 1), ensuring that the larger numbers fall into the odd indices.
  3. Perform a three-way partition (Dutch National Flag approach) on the array using the virtual index. Use three pointers (left, current, right) to swap elements in-place:
    • If the element at the virtual index is greater than the median, swap it with the left pointer’s element.
    • If it is less than the median, swap it with the right pointer’s element.
    • Otherwise, move the pointer forward. This rearrangement guarantees that the wiggle order (nums[0] < nums[1] > nums[2] < nums[3]...) is achieved.

Code Solutions

def wiggleSort(nums):
    """
    Rearranges nums into wiggle order in-place.
    """
    n = len(nums)
    # Step 1: Find the median
    # Here, we use sorting for simplicity.
    sorted_nums = sorted(nums)
    median = sorted_nums[n // 2]

    # Virtual index mapping function
    def new_index(i):
        # Maps index to a virtual index to meet wiggle order constraints.
        return (1 + 2 * i) % (n | 1)

    # Three-way partitioning with Dutch National Flag approach.
    left, i, right = 0, 0, n - 1
    while i <= right:
        ni = new_index(i)
        if nums[ni] > median:
            nleft = new_index(left)
            # Swap current element with element at left pointer.
            nums[ni], nums[nleft] = nums[nleft], nums[ni]
            left += 1
            i += 1
        elif nums[ni] < median:
            nright = new_index(right)
            # Swap current element with element at right pointer.
            nums[ni], nums[nright] = nums[nright], nums[ni]
            right -= 1
        else:
            i += 1

# Example usage:
nums = [1,5,1,1,6,4]
wiggleSort(nums)
print(nums)  # Output may be [1,6,1,5,1,4] or another valid wiggle order.
← Back to All Questions