In this guide, you will get 324. Wiggle Sort II LeetCode Solution with the best time and space complexity. The solution to Wiggle Sort II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Given an integer array nums, reorder it such that nums[0] nums[2] < nums[3]….
You may assume the input array always has a valid answer.
Example 1:
Input: nums = [1,5,1,1,6,4]
Output: [1,6,1,5,1,4]
Explanation: [1,4,1,5,1,6] is also accepted.
Example 2:
Input: nums = [1,3,2,2,3,1]
Output: [2,3,1,3,1,2]
Constraints:
1 <= nums.length <= 5 * 104
0 <= nums[i] <= 5000
It is guaranteed that there will be an answer for the given input nums.
Follow Up: Can you do it in O(n) time and/or in-place with O(1) extra space?
Complexity Analysis
Time Complexity: O(n) \to O(n^2)
Space Complexity: O(1)
324. Wiggle Sort II LeetCode Solution in C++
class Solution {
public:
void wiggleSort(vector<int>& nums) {
const int n = nums.size();
const auto it = nums.begin() + n / 2;
nth_element(nums.begin(), it, nums.end());
const int median = *it;
// index-rewiring
#define A(i) nums[(1 + 2 * i) % (n | 1)]
for (int i = 0, j = 0, k = n - 1; i <= k;)
if (A(i) > median)
swap(A(i++), A(j++));
else if (A(i) < median)
swap(A(i), A(k--));
else
++i;
}
};
/* code provided by PROGIEZ */
324. Wiggle Sort II LeetCode Solution in Java
class Solution {
public void wiggleSort(int[] nums) {
final int n = nums.length;
final int median = findKthLargest(nums, (n + 1) / 2);
for (int i = 0, j = 0, k = n - 1; i <= k;)
if (nums[A(i, n)] > median)
swap(nums, A(i++, n), A(j++, n));
else if (nums[A(i, n)] < median)
swap(nums, A(i, n), A(k--, n));
else
++i;
}
private int A(int i, int n) {
return (1 + 2 * i) % (n | 1);
}
// Same as 215. Kth Largest Element in an Array
private int findKthLargest(int[] nums, int k) {
return quickSelect(nums, 0, nums.length - 1, k);
}
private int quickSelect(int[] nums, int l, int r, int k) {
final int pivot = nums[r];
int nextSwapped = l;
for (int i = l; i < r; ++i)
if (nums[i] >= pivot)
swap(nums, nextSwapped++, i);
swap(nums, nextSwapped, r);
final int count = nextSwapped - l + 1; // the number of `nums` >= pivot
if (count == k)
return nums[nextSwapped];
if (count > k)
return quickSelect(nums, l, nextSwapped - 1, k);
return quickSelect(nums, nextSwapped + 1, r, k - count);
}
private void swap(int[] nums, int i, int j) {
final int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
// code provided by PROGIEZ
324. Wiggle Sort II LeetCode Solution in Python
class Solution:
def wiggleSort(self, nums: list[int]) -> None:
n = len(nums)
median = self._findKthLargest(nums, (n + 1) // 2)
def A(i: int):
return (1 + 2 * i) % (n | 1)
i = 0
j = 0
k = n - 1
while i <= k:
if nums[A(i)] > median:
nums[A(i)], nums[A(j)] = nums[A(j)], nums[A(i)]
i, j = i + 1, j + 1
elif nums[A(i)] < median:
nums[A(i)], nums[A(k)] = nums[A(k)], nums[A(i)]
k -= 1
else:
i += 1
# Same as 215. Kth Largest Element in an Array
def _findKthLargest(self, nums: list[int], k: int) -> int:
def quickSelect(l: int, r: int, k: int) -> int:
randIndex = random.randint(0, r - l) + l
nums[randIndex], nums[r] = nums[r], nums[randIndex]
pivot = nums[r]
nextSwapped = l
for i in range(l, r):
if nums[i] >= pivot:
nums[nextSwapped], nums[i] = nums[i], nums[nextSwapped]
nextSwapped += 1
nums[nextSwapped], nums[r] = nums[r], nums[nextSwapped]
count = nextSwapped - l + 1 # Number of nums >= pivot
if count == k:
return nums[nextSwapped]
if count > k:
return quickSelect(l, nextSwapped - 1, k)
return quickSelect(nextSwapped + 1, r, k - count)
return quickSelect(0, len(nums) - 1, k)
# code by PROGIEZ
