✅Wavy Array

Wave Array - InterviewBitInterviewBit

Given an array of integers, sort the array into a wave-like array and return it, In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5.....

Using Sorting and Swap Alternate (Most Optimal)

vector<int> Solution::wave(vector<int> &A) {
    sort(A.begin(), A.end());
    for(int i = 0; i + 1 < A.size(); i += 2) 
        swap(A[i], A[i + 1]);

    return A;
}

Time Complexity: $O(n \log n)$​

Space Complexity: $O(1)$​