This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

Given an unsorted array `nums`

, reorder it **in-place** such that `nums[0] <= nums[1] >= nums[2] <= nums[3]...`

.

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\n\n

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

\n\n\n\n

'
\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

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

**Complexity analysis**

- \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

\n`heapsort`

is used. \n

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

\npublic 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

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.

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

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

\npublic 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

**Complexity analysis**

- \n
- \n
Time complexity : .\nIn the worst case we swap at most times. An example input is

\n`[2,1,3,1,4,1]`

. \n - \n
Space complexity : .

\n \n