Problem
Given an unsorted array nums
, reorder it in-place such that
|
|
Examples
Example 1:
|
|
Example 2:
|
|
Similar Problems
Wiggle Sort 2 - No Adjacent Duplicates
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:
|
|
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
|
|
|
|
|
|
Complexity
- ⏰ Time complexity:
O(n)
, where n is the length of the array. - 🧺 Space complexity:
O(1)
, as the sorting is done in-place.