379. Wiggle Sort
Given an integer array nums, reorder it such that nums[0] <= nums[1] >= nums[2] <= nums[3]....
You may assume the input array always has a valid answer.
Example 1:
Input: nums = [3,5,2,1,6,4]
Explanation: We need to ensure that elements alternate between ≤ and ≥. Start from index 1 and adjust if needed. 3 ≤ 5 (correct), 5 ≥ 2 (correct), 2 ≤ 1 (incorrect) → swap 2 and 1, now nums = [3,5,1,2,6,4]. Next, 2 ≤ 6 (correct), 6 ≥ 4 (correct).
Output: [3,5,1,6,2,4].
Another valid answer: [1,6,2,5,3,4].
Example 2:
Input: nums = [6,6,5,6,3,8]
Output: [6,6,5,6,3,8]
Explanation: Check alternating conditions: 6 ≤ 6 (correct), 6 ≥ 5 (correct), 5 ≤ 6 (correct), 6 ≥ 3 (correct), 3 ≤ 8 (correct). Since all conditions are already satisfied, no swaps are needed. Final output: [6,6,5,6,3,8].
Now Your Turn!
Pick the correct output for the given inputInput : nums = [5,4,3,2,1]
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= nums.length <= 5 * 104
- 0 <= nums[i] <= 104
- It is guaranteed that there will be an answer for the given input nums.