<p>Given an integer array <code>nums</code>, reorder it such that <code>nums[0] &lt; nums[1] &gt; nums[2] &lt; nums[3]...</code>.</p>

<p>You may assume the input array always has a valid answer.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,5,1,1,6,4]
<strong>Output:</strong> [1,6,1,5,1,4]
<strong>Explanation:</strong> [1,4,1,5,1,6] is also accepted.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [1,3,2,2,3,1]
<strong>Output:</strong> [2,3,1,3,1,2]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= nums.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>0 &lt;= nums[i] &lt;= 5000</code></li>
	<li>It is guaranteed that there will be an answer for the given input <code>nums</code>.</li>
</ul>

<p>&nbsp;</p>
<strong>Follow Up:</strong> Can you do it in <code>O(n)</code> time and/or <strong>in-place</strong> with <code>O(1)</code> extra space?
class Solution {
public:
    void wiggleSort(vector<int>& nums) {
        int n = nums.size();
        
        // Find the median of the array.
        // nth_element rearranges the array such that all elements before the nth element are smaller,
        // and all elements after the nth element are larger. The nth element is positioned correctly,
        // but the order of elements on either side is not guaranteed to be sorted.
        auto midptr = nums.begin() + n / 2;
        nth_element(nums.begin(), midptr, nums.end());
        int mid = *midptr; // The median element

        // This lambda function is used to "rewire" the array indices in a virtual order.
        // The purpose is to index elements in a way that we can easily place larger elements
        // at the odd indices and smaller elements at even indices, resulting in a wiggle pattern.
        // We use (1 + 2 * i) % (n | 1) for this reordering.
        // (n | 1) ensures that we handle odd and even-sized arrays uniformly.
        #define A(i) nums[(1 + 2 * (i)) % (n | 1)]

        // Now, we need to partition the array into three parts using a 3-way partitioning approach:
        // 1. Elements greater than the median.
        // 2. Elements equal to the median.
        // 3. Elements less than the median.

        int i = 0, j = 0, k = n - 1; // We use three pointers for this.
        while (j <= k) {
            if (A(j) > mid) {
                // If the current element is greater than the median,
                // place it in the 'larger half' section by swapping it with the element at index i.
                swap(A(i++), A(j++));
            } else if (A(j) < mid) {
                // If the current element is smaller than the median,
                // place it in the 'smaller half' section by swapping it with the element at index k.
                swap(A(j), A(k--));
            } else {
                // If the current element equals the median, just move to the next element.
                j++;
            }
        }
    }
};

19700