/324. Wiggle Sort II

324. Wiggle Sort II

Medium

Arrays37.1% acceptance

Given a list of integers arr, rearrange the elements in-place so that arr[0] < arr[1] > arr[2] < arr[3] ... for all valid indices. Multiple valid outputs may exist. The function should modify arr in-place and not return anything.

Example 1

Input: [2,7,2,8,2,9]

Output: [2,8,2,9,2,7]

Explanation: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < arr[5] holds.

Example 2

Input: [4,4,5,5,6,6]

Output: [4,6,4,6,5,5]

Explanation: arr[0] < arr[1] > arr[2] < arr[3] > arr[4] < arr[5] holds.

Constraints

1 <= len(arr) <= 50000
0 <= arr[i] <= 5000 for all i
There is always at least one valid arrangement

Python (current runtime)

Case 1

Input: [3,1,4,1,5,9]

Expected: [1,4,1,5,3,9]

Case 2

Input: [10,10,11,11,12,12]

Expected: [10,12,10,12,11,11]

Case 3

Input: [0,0,1,1,2,2]

Expected: [0,1,0,2,1,2]