🎨Now live: Try our Free AI Image Generation Feature

Description
The task is to reorder an unsorted array nums
such that nums[0] < nums[1] > nums[2] < nums[3]...
(this is known as wiggle sort). This means that the elements at even indices should be less than their neighboring odd indices, and elements at odd indices should be greater than their neighbors.
Intuition
By sorting the array, we can easily place smaller numbers in the even positions and larger numbers in the odd positions. This ensures that the wiggle property is satisfied: numbers at odd positions are greater than their neighbors and numbers at even positions are smaller. The key is to rearrange the array by alternating between the two halves of the sorted array.
Approach
- Sort the Array: First, sort the array to arrange the elements in increasing order.
- Partition the Array: Calculate the middle index to divide the array into two halves: - Left half for the even indices (smaller numbers). - Right half for the odd indices (larger numbers).
- Rearrange: Start filling the
nums
array by alternately taking elements from the left and right halves of the sorted array. - Final Structure: Place the smaller numbers from the left half of the sorted array in the even indices and the larger numbers from the right half in the odd indices.
Complexity
Time Complexity:
- Sorting the array takes (O(n \log n)), where
n
is the number of elements. - Rearranging the elements takes (O(n)).
- Hence, the overall time complexity is (O(n \log n)).
Space Complexity:
- We use an additional array to store the sorted version of
nums
, which takes (O(n)) space. - Therefore, the space complexity is (O(n)).
Code
C++
class Solution {
public:
void wiggleSort(std::vector& nums) {
std::vector sorted(nums);
std::sort(sorted.begin(), sorted.end());
int mid = (nums.size() + 1) / 2;
int j = mid - 1;
int k = nums.size() - 1;
for (int i = 0; i < nums.size(); i++) {
if (i % 2 == 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
}
};
Python
class Solution:
def wiggleSort(self, nums):
sorted_nums = sorted(nums)
mid = (len(nums) + 1) // 2
j, k = mid - 1, len(nums) - 1
for i in range(len(nums)):
if i % 2 == 0:
nums[i] = sorted_nums[j]
j -= 1
else:
nums[i] = sorted_nums[k]
k -= 1
Java
class Solution {
public void wiggleSort(int[] nums) {
int[] sorted = nums.clone();
Arrays.sort(sorted);
int mid = (nums.length + 1) / 2;
int j = mid - 1;
int k = nums.length - 1;
for (int i = 0; i < nums.length; i++) {
if (i % 2 == 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
}
}
JavaScript
var wiggleSort = function (nums) {
nums.sort((a, b) => a - b);
let sorted = nums.slice();
let mid = Math.floor((nums.length + 1) / 2);
let j = mid - 1;
let k = nums.length - 1;
for (let i = 0; i < nums.length; i++) {
if (i % 2 === 0) {
nums[i] = sorted[j--];
} else {
nums[i] = sorted[k--];
}
}
};