Problem
Given an unsorted array nums
, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]...
.
Examples
Example 1
|
|
Example 2
|
|
Constraints
1 <= nums.length <= 5 * 10^4
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?
Similar Problems
Solution
Method 1 – Median Partitioning with Index Mapping
We previously discussed wiggle sort where adjacent duplicates were allowed, but that approach fails here since equal elements cannot be next to each other.
Intuition
The key idea is to rearrange the array so that no two adjacent elements are equal and the wiggle property (nums[0] < nums[1] > nums[2] < nums[3]...
) holds. By finding the median and partitioning the array around it, then cleverly mapping indices, we can achieve the desired order in-place.
To solve this, consider a sorted array like [1, 2, 3, 4, 5, 6, 7, 8, 9]
by splitting it around the median, we can interleave elements from the lower and upper halves to achieve the wiggle order.
For instance, after partitioning around the median which is 5
, we can partition elements into 3 parts - 1) left part containing elements greater than median, 2) middle part is equal to median and 3)right part contains elements less than median.
Now, we can take one element from each partition, i.e. pick one from middle, one from left and then one from right. Then, we will get the array as [5, 9, 4, 8, 3, 7, 2, 6, 1]
.
Approach
So, the approach can be:
- Find the Median: Use QuickSelect to find the median of the array in O(n) time. Here is the logic if you understand how it works - Kth smallest element using Randomized Selection OR Order Statistics OR QuickSelect.
- Index Mapping: Map the original indices to new positions using
(1 + 2*i) % (n | 1)
to ensure large and small numbers alternate. - Three-way Partitioning: This is where we can apply the Dutch National Flag (DNF) problem OR Three color sort (3-way partitioning) algorithm using the mapped indices to partition the array into elements greater than, equal to, and less than the median, but we have to apply it in reverse order, placing larger elements to the left and smaller ones on right. This process runs in O(n) time and uses O(1) extra space.
- In-place Rearrangement: Swap elements in-place according to the mapped indices to achieve the wiggle order.
Dry Run
Here comes the fun part. We actually can do a wiggle sort in the shadow of DNF sort if we carefully map the index of DNF sort into index of wiggle sort. For example,
|
|
Code
|
|
|
|
|
|
Complexity
- ⏰ Time complexity: O(n) for median finding (QuickSelect) and O(n) for partitioning, so overall O(n).
- 🧺 Space complexity: O(1) for in-place approach (C++), O(n) for extra array (Java/Python shown above for clarity).