How to solve a wiggle sort problem in C++

Solution explanation

Our task is to reorder the given array so that each element at an odd index is either greater than or equal to the elements at its adjacent even indices, creating a wiggle pattern.

One intuitive approach to achieve this is to initially sort the nums array. Then, for every element at an odd index, for example, i, we swap it with its adjacent element at the index i+1. While this approach would work, it has a time complexity of $O(nlogn)$ .

However, we can solve this problem more efficiently using the greedy algorithm. The core idea behind the greedy approach is to recognize that for a wiggle pattern, adjacent elements should alternate between being larger and smaller than each other. As we iterate through the array, we make swaps whenever adjacent elements don’t satisfy this condition, gradually transforming the array into the desired wiggle pattern.

Here’s how the logic works:

If the current index is even, we check if the current element is larger than the next one. If so, we swap them to make the current element smaller than the next one.
If the current index is odd, we check if the current element is smaller than the next one. If so, we swap them to make the current element larger than the next one.

By following this logic, elements naturally fall into the desired pattern as we iterate through the array. This approach is highly efficient and requires only a single pass through the array to achieve the result.

Code implementation

Let’s look at the code for the logic discussed above.

#include <iostream>
#include <vector>
//Function to swap two integers in an array
void swap(std::vector<int>& nums, int i, int j) {
  int temp = nums[i];
  nums[i] = nums[j];
  nums[j] = temp;
}
//Function to rearrange the array in wiggle pattern
void wiggleSort(std::vector<int>& nums) {
  //Calculate the size of an array
  int n = nums.size();
  //Iterate through an array
  for (int i = 0; i < n - 1; i++) {
    // Check if the current index is even and the current element is greater than the next one
    // or if the current index is odd and the current element is smaller than the next one
    if ((i % 2 == 0 && nums[i] > nums[i + 1]) ||
        (i % 2 == 1 && nums[i] < nums[i + 1])) {
          //Call the swap function to place the current indices in their desired place
          swap(nums, i, i+1);
    }
  }
}
int main() {
  //Input array
  std::vector<int> nums = {3, 5, 2, 1, 6, 4};
  //Print the original array
  std::cout << "Original Array: ";
  for (int num : nums) {
      std::cout << num << " ";
  }
  std::cout << std::endl;
  
  //Call the wiggle function
  wiggleSort(nums);
  //Print the sorted array
  std::cout << "Wiggle Sorted Array: ";
  for (int num : nums) {
      std::cout << num << " ";
  }
  std::cout << std::endl;
  return 0;
}

Complexity analysis

Now, we’ll analyze the space and time complexity of the code above. Let n be the size of the input array nums.

Time complexity

The primary operation in this code is the loop that iterates through the array. The loop runs for (n-1) iterations. Therefore, the overall time complexity of the wiggleSort function is $O(n)$ .

Space complexity

The space complexity of a function is determined by the additional space used to store the input array nums. Since we don’t use any additional data structures that depend on the size of the input, the space complexity is $O(n)$ .

Free AI Mock Interviews

Coding Interview

Coding PatternsFree Interview

Gain insights and practical experience with coding patterns through targeted MCQs and coding problems, designed to match and challenge your expertise level.

System Design

YouTubeFree Interview

Learn to design a video streaming platform like YouTube by tackling functional and non-functional requirements, core components, and high-level to detailed design challenges.

Free Resources