Wiggle Sort - Leetcode Solution

Problem Statement:

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

Example 1:

Input: nums = [3,5,2,1,6,4] Output: [3,5,1,6,2,4] Explanation: This example follows the wiggle sort style.

Example 2:

Input: nums = [1,3,2,2,3,1] Output: [2,3,1,3,1,2]

Approach:

The idea of the problem is to arrange the elements in a wavy pattern. We can achieve this by swapping the elements at required positions. The first step is to sort the array. If we sort the array, then the elements are arranged in an ascending order. We can then swap the adjacent elements to get the required wavy pattern.

Algorithm:

1. Sort the given array in an ascending order.
2. Traverse through the array starting from the second element.
3. If the index of the element is even and the value of the current element is greater than the previous element, then swap the current and previous elements.
4. If the index of the element is odd and the value of the current element is less than the previous element, then swap the current and previous elements.
5. Return the sorted and wavy pattern array.

Code:

class Solution { public: void wiggleSort(vector<int>& nums) { sort(nums.begin(), nums.end()); for(int i=1; i<nums.size()-1; i+=2){ swap(nums[i], nums[i+1]); } } };

Time Complexity: O(nlogn) - Sorting takes O(nlogn) time. Space Complexity: O(1) - The swapping is done in-place.

1