Solving Wiggle Sort II in go. Please try yourself first to solve the problem and submit your implementation to LeetCode before looking into solution.

## Problem Description

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

Example 1:

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

Example 2:

``````Input: nums = [1, 3, 2, 2, 3, 1]
Output: One possible answer is [2, 3, 1, 3, 1, 2].``````

Note:

You may assume all input has valid answer.

Can you do it in O(n) time and/or in-place with O(1) extra space?

``````Index :       0   1   2   3   4   5
Small half:   M       S       S
Large half:       L       L       L(M)``````
``````13   6   5   5   4   2

M``````
``````Step 1:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    5    5    4    2
Left
i
Right``````
``````Step 2:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    5    5    4    2
Left
i
Right``````
``````Step 3:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    5    5    4    2
Left
i
Right``````
``````Step 4:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    5    5    2    4
Left
i
Right``````
``````Step 5:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    4    5    2    5
Left
i
Right``````
``````Step 6:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        13   6    4    5    2    5
Left
i
Right``````
``````Step Final:
Original idx: 0    1    2    3    4    5
Mapped idx:   1    3    5    0    2    4
Array:        5    6    4    13   2    5
Left
i
Right``````

See the full details of the problem Wiggle Sort II at LeetCode

Originally posted at: @github.com/halfrost/LeetCode-Go