algoadvance

Leetcode 324. Wiggle Sort II

Problem Statement

Given an integer array nums, reorder it such that nums[0] < nums[1] > nums[2] < nums[3].... This is known as the Wiggle Sort. Specifically, we need to rearrange the elements to satisfy the following conditions:

The resulting array should alternate between peaks and valleys.

Example

Input: nums = [1, 5, 1, 1, 6, 4]
Output: [1, 6, 1, 5, 1, 4]

Clarifying Questions

  1. Q: Can we modify the array in place? A: Yes, in-place modifications are allowed.
  2. Q: Are there any constraints on the length of the array? A: The length of the array can be up to 5000.
  3. Q: What should be done if the array has multiple correct solutions? A: Any solution that satisfies the conditions is acceptable.

Strategy

  1. Sort the Array: First, sort the array. This makes it easier to reorder the elements to achieve the “wiggle” condition.
  2. Split into Two Halves: Divide the sorted array into two halves.
  3. Interleave Elements: Interleave elements from the two halves such that elements from the first half are placed in odd indices (0-based) and elements from the second half in even indices. This helps in maintaining the wiggle condition.
  4. Reverse Traversal: To place larger elements first, we can traverse the two halves in reverse order while interleaving them.

Code

#include <algorithm>
#include <vector>

void wiggleSort(std::vector<int>& nums) {
    // Step 1: Sort the array
    std::vector<int> sorted(nums);
    std::sort(sorted.begin(), sorted.end());
    
    int n = nums.size();
    int left = (n + 1) / 2 - 1; // End of the first half
    int right = n - 1;          // End of the second half
    
    // Step 2: Interleave elements in the original array
    for (int i = 0; i < n; ++i) {
        if (i % 2 == 0) {
            nums[i] = sorted[left--];
        } else {
            nums[i] = sorted[right--];
        }
    }
}

Time Complexity

  1. Sorting: The std::sort function has a time complexity of ( O(n \log n) ).
  2. Interleaving: This is done in a single pass over the array, which has a time complexity of ( O(n) ).

Hence, the overall time complexity is ( O(n \log n) ).

Explanation

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI