Vultr DocsLatest Content

Wiggle Sort

Updated on 03 July, 2025
Wiggle Sort header image

Problem Statement

Given an integer array nums, the goal is to reorder the elements of the array so that it follows a specific pattern: nums[0] <= nums[1] >= nums[2] <= nums[3]... and so forth. This particular sequence of inequalities ensures that every even-indexed element (starting from zero) is less than or equal to the next, and every odd-indexed element is greater than or equal to the next. It is important not to feel restricted by just one specific pattern as there can be multiple valid reordering answers that satisfy the condition.

Examples

Example 1

Input:

nums = [3,5,2,1,6,4]

Output:

[3,5,1,6,2,4]

Explanation:

[1,6,2,5,3,4] is also accepted.

Example 2

Input:

nums = [6,6,5,6,3,8]

Output:

[6,6,5,6,3,8]

Constraints

  • 1 <= nums.length <= 5 * 104
  • 0 <= nums[i] <= 104
  • It is guaranteed that there will be an answer for the given input nums.

Approach and Intuition

  1. Understanding the problem: The primary requirement is to reorder the array such that its elements alternately follow a "less than or equal to" and "greater than or equal to" pattern. Think of it as a valley-peak structure where elements alternatively ascend and descend.

  2. Insight into the pattern:

    • When we need nums[0] <= nums[1], and then nums[1] >= nums[2], swapping elements suffices if they do not originally meet the requirement. If we look closely, we need to make sure that for all even indices i, nums[i] should not be greater than nums[i+1] and for odd indices, nums[i] should not be less than nums[i+1].

  3. Approach to Solution:

    • Iterative Adjustment: Traverse the array and for each index i, check if the current and the next element satisfy the required relationship based on whether i is even or odd. If they don't, simply swap nums[i] and nums[i+1].
    • This swapping ensures that the preceding condition is locally satisfied, and since we are iterating over the entire array, we make successive adjustments to satisfy the global condition.

  4. Reasoning for validity: The constraints ensure that there exists at least one valid reordering for the array. Thus, the approach of iterative adjustment is guaranteed to work. This method takes linear time, which is efficient given the input size constraint up to 50,000.

This approach is akin to a simplified bubble sort where instead of aiming for a complete sort, you're ensuring that the pattern constraints are adhered to by continuously swapping non-conforming adjacent elements. By taking advantage of the guarantee provided in the problem, this method remains simple yet efficient.

Solutions

  • C++
cpp 
class Solution {
public:
    void exchangeElements(vector<int>& arr, int x, int y) {
        int temporary = arr[x];
        arr[x] = arr[y];
        arr[y] = temporary;
    }
    
    void sortWiggle(vector<int>& arr) {
        for (int idx = 0; idx < arr.size() - 1; idx++) {
            if (((idx % 2 == 0) && arr[idx] > arr[idx + 1]) ||
                ((idx % 2 == 1) && arr[idx] < arr[idx + 1])) {
                exchangeElements(arr, idx, idx + 1);
            }
        }
    }
};

This solution aims to rearrange elements in an array to satisfy the wiggle sort condition. Wiggle sort dictates that the numbers must alternate between being greater and less than each other, which looks like: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < ... for an array arr.

The provided algorithm is implemented in C++ and contains two main functions within a class named Solution:

  • exchangeElements(vector<int>& arr, int x, int y)

    • This function swaps elements in the array arr at indices x and y. A temporary variable is used to hold the value during the swap process.

  • sortWiggle(vector<int>& arr)

    • This function sorts the array into a wiggle pattern. It iterates through each element in the array, checking the current index idx to determine the required relationship (less than or greater than) with the next element. For indices where:
      • idx is even: If the element is greater than the next element (arr[idx] > arr[idx + 1]), it invokes the exchangeElements method to swap them.
      • idx is odd: If the element is less than the next element (arr[idx] < arr[idx + 1]), it performs the swap using the same method.

The approach operates in a single pass through the array (O(n) time complexity), adjusting neighboring elements to ensure the entire array fits the wiggle condition. This method is efficient for rearranging any sequence with variable lengths, utilizing controlled swapping based on conditional checking of index parity (even or odd). By handling edge cases within the loop, the function effectively enforces the wiggle pattern without needing a separate sorting step, making it suitable for applications requiring quick, in-place sorting in an alternating pattern.

  • Java
java 
class Solution {
    public void interchange(int[] arr, int index1, int index2) {
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
    public void wiggleArrangeArray(int[] arr) {
        for (int index = 0; index < arr.length - 1; index++) {
            if (((index % 2 == 0) && arr[index] > arr[index + 1])
                    || ((index % 2 == 1) && arr[index] < arr[index + 1])) {
                interchange(arr, index, index + 1);
            }
        }
    }
}

The solution provided here addresses the problem of rearranging an array into a "wiggle" pattern where the numbers alternate between being greater than and less than their immediate neighbors. Here's a breakdown of how the Java solution achieves this:

  • An interchange method swaps two elements in an array, given their indices. This method uses a temporary variable to facilitate the swap between the two elements.

  • The wiggleArrangeArray method is the primary function that rearranges the array into the desired pattern. The method iterates through the array, checking each element:

    • If the current index is even, and the current element is greater than the next, a swap is performed.
    • If the current index is odd, and the current element is less than the next, a swap is also performed.

This approach ensures that each element at an even index is less than the one following it, and each element at an odd index is greater than the one following it, complying with the wiggle sort pattern requirements. This method handles the pairwise comparison and rearrangement efficiently and modifies the array in place, making it space efficient.

Comments

No comments yet.