Problem

Given an unsorted array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3]....

Examples

Example 1

1
2

Input: nums = [1, 5, 1, 1, 6, 4]
Output: One possible answer is [1, 4, 1, 5, 1, 6].

Example 2

1
2

Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 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

Wiggle Sort 1

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:

  1. 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.
  2. Index Mapping: Map the original indices to new positions using (1 + 2*i) % (n | 1) to ensure large and small numbers alternate.
  3. 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.
  4. 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,

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

DNF order: [9,8,7,6 5, 4,3,2,1]
DNF Index: [0,1,2,3, 4, 5,6,7,8]

Wiggle order: [5, 9, 4, 8, 3, 7, 2, 6, 1]
Wiggle Index: [0, 1, 2, 3, 4, 5, 6, 7, 8]

Index Mapping:
---------------
DNF --> Wiggle (value)
-----------------------
0 --> 1 (9)
1 --> 3 (8)
2 --> 5 (7)
3 --> 7 (6)
4 --> 0 (5)
5 --> 2 (4)
6 --> 4 (3)
7 --> 6 (2)
8 --> 8 (1)

that is DNF(i) = WIGGLE((1+2*i)%n)

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        auto findKth = [&](int k) {
            vector<int> arr = nums;
            nth_element(arr.begin(), arr.begin() + k, arr.end());
            return arr[k];
        };
        int median = findKth(n / 2);

        auto idx = [&](int i) { return (1 + 2 * i) % (n | 1); };

        int i = 0, j = 0, k = n - 1;
        while (j <= k) {
            if (nums[idx(j)] > median) {
                swap(nums[idx(i++)], nums[idx(j++)]);
            } else if (nums[idx(j)] < median) {
                swap(nums[idx(j)], nums[idx(k--)]);
            } else {
                j++;
            }
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
    public void wiggleSort(int[] nums) {
        int n = nums.length;
        int[] arr = nums.clone();
        Arrays.sort(arr);
        int median = arr[(n - 1) / 2];

        int left = (n - 1) / 2, right = n - 1;
        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                ans[i] = arr[left--];
            } else {
                ans[i] = arr[right--];
            }
        }
        System.arraycopy(ans, 0, nums, 0, n);
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def wiggleSort(self, nums: list[int]) -> None:
        n = len(nums)
        arr = sorted(nums)
        ans = [0] * n
        l, r = (n - 1) // 2, n - 1
        for i in range(n):
            if i % 2 == 0:
                ans[i] = arr[l]
                l -= 1
            else:
                ans[i] = arr[r]
                r -= 1
        nums[:] = ans

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).