## 280. Wiggle Sort

Given an unsorted array nums, reorder it in-place such that nums <= nums >= nums <= nums....

For example, given nums = [3, 5, 2, 1, 6, 4], one possible answer is [1, 6, 2, 5, 3, 4].

b'
\n\n

## Solution

\n
\n

#### Approach #1 (Sorting) [Accepted]

\n

The obvious solution is to just sort the array first, then swap elements pair-wise starting from the second element. For example:

\n
   [1, 2, 3, 4, 5, 6]\n       \xe2\x86\x91  \xe2\x86\x91  \xe2\x86\x91  \xe2\x86\x91\n       swap  swap\n\n=> [1, 3, 2, 5, 4, 6]\n
\n
public void wiggleSort(int[] nums) {\n    Arrays.sort(nums);\n    for (int i = 1; i < nums.length - 1; i += 2) {\n        swap(nums, i, i + 1);\n    }\n}\n\nprivate void swap(int[] nums, int i, int j) {\n    int temp = nums[i];\n    nums[i] = nums[j];\n    nums[j] = temp;\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nThe entire algorithm is dominated by the sorting step, which costs time to sort elements.

\n
• \n
• \n

Space complexity : . Space depends on the sorting implementation which, usually, costs auxiliary space if heapsort is used.

\n
• \n
\n
\n

#### Approach #2 (One-pass Swap) [Accepted]

\n

Intuitively, we should be able to reorder it in one-pass. As we iterate through the array, we compare the current element to its next element and if the order is incorrect, we swap them.

\n
public void wiggleSort(int[] nums) {\n    boolean less = true;\n    for (int i = 0; i < nums.length - 1; i++) {\n        if (less) {\n            if (nums[i] > nums[i + 1]) {\n                swap(nums, i, i + 1);\n            }\n        } else {\n            if (nums[i] < nums[i + 1]) {\n                swap(nums, i, i + 1);\n            }\n        }\n        less = !less;\n    }\n}\n
\n

We could shorten the code further by compacting the condition to a single line. Also observe the boolean value of less actually depends on whether the index is even or odd.

\n
public void wiggleSort(int[] nums) {\n    for (int i = 0; i < nums.length - 1; i++) {\n        if (((i % 2 == 0) && nums[i] > nums[i + 1])\n                || ((i % 2 == 1) && nums[i] < nums[i + 1])) {\n            swap(nums, i, i + 1);\n        }\n    }\n}\n
\n

Here is another amazing solution by @StefanPochmann who came up with originally here.

\n
public void wiggleSort(int[] nums) {\n    for (int i = 0; i < nums.length - 1; i++) {\n        if ((i % 2 == 0) == (nums[i] > nums[i + 1])) {\n            swap(nums, i, i + 1);\n        }\n    }\n}\n
\n

Complexity analysis

\n
\n
• \n

Time complexity : .\nIn the worst case we swap at most times. An example input is [2,1,3,1,4,1].

\n
• \n
• \n

Space complexity : .

\n
• \n
\n
'