Wiggle Sort 1

Problem

Given an unsorted array nums, reorder it in-place such that

nums[0] <= nums[1] >= nums[2] <= nums[3]....

Examples

Example 1:

Input: [3, 5, 2, 1, 6, 4]
Output: [1, 6, 2, 5, 3, 4]
Explanation: This question may have multiple answers, and [2, 6, 1, 5, 3, 4] is also ok.

Example 2:

Input: [1, 2, 3, 4]
Output: [1, 4, 2, 3]

Solution

Method 1 - Sorting the Array

We can sort the array and then check each adjacent pair to ensure the wiggle property, resulting in a time complexity of O(n log n). However, is there a more efficient approach?

Method 2 - Swapping Odd and Even Pairs to Match the Condition

If we examine the problem, we notice that ensuring each pair of consecutive elements follows the wiggle pattern (A[i-1] <= A[i] >= A[i+1]) guarantees the property for their neighbors as well. This allows us to simply check even and odd indices:

A[even] <= A[odd]
A[odd] >= A[even]

We can iterate through the array, swapping elements whenever this condition is violated, resulting in an O(n) solution. Start from index 1 since index 0 has no previous element. To check if an index is odd, use either i % 2 == 1 or i & 1 == 1.

Code

C++

void wiggleSort(vector<int>& nums) {
	for (int i = 1; i < nums.size(); ++i) {
		bool isOdd = i % 2 == 1;
		if ((isOdd && nums[i] < nums[i-1]) ||
			(!isOdd && nums[i] > nums[i-1])) {
			swap(nums[i], nums[i-1]);
		}
	}
}

Java

public static void wiggleSort(int[] nums) {
	for (int i = 1; i < nums.length; i++) {
		boolean isOdd = (i & 1) == 1;
		if ((isOdd && nums[i] < nums[i-1]) ||
			(!isOdd && nums[i] > nums[i-1])) {
			int temp = nums[i];
			nums[i] = nums[i-1];
			nums[i-1] = temp;
		}
	}
}

Python

def wiggleSort(nums):
	for i in range(1, len(nums)):
		is_odd = i % 2 == 1
		if (is_odd and nums[i] < nums[i-1]) or (not is_odd and nums[i] > nums[i-1]):
			nums[i], nums[i-1] = nums[i-1], nums[i]

Complexity

⏰ Time complexity: O(n), where n is the length of the array.
🧺 Space complexity: O(1), as the sorting is done in-place.