Wiggle Sort Ii - Leetcode Solution

Problem statement: 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: [1,6,1,5,1,4] Explanation: This is a zigzag like pattern.

Approach: To solve this problem, we have to first sort the array using two pointers method (quick sort) then change the sequences to satisfy the required condition. In the required condition, if we look at the sequence, the even index should have the value greater or equal than the previous odd index value and less or equal to the next odd index value. The same applies to the odd index values.

Algorithm:

1. Sort the array.
2. Set two pointers p1 and p2 at index (n-1)/2 and n-1, respectively.
3. Create a new array result.
4. For each element in the result array, if the index is even, assign nums[p1] to it and decrement p1. If the index is odd, assign nums[p2] to it and decrement p2.
5. Return the result.

Pseudo code: def wiggleSort(nums): nums.sort() p1 = (len(nums)-1)//2 p2 = len(nums)-1 result = [0] * len(nums) for i in range(len(nums)): if i % 2 == 0: result[i] = nums[p1] p1 -= 1 else: result[i] = nums[p2] p2 -= 1 return result

Time complexity: O(nlogn) due to sorting the array. Space complexity: O(n) for creating a new array for the result.

Code in Python:

class Solution: def wiggleSort(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ nums.sort() p1 = (len(nums)-1)//2 p2 = len(nums)-1

    result = [0] * len(nums)
    for i in range(len(nums)):
        if i % 2 == 0:
            result[i] = nums[p1]
            p1 -= 1
        else:
            result[i] = nums[p2]
            p2 -= 1

    nums[:] = result[:] # Update nums with the result

1