Alternative Sorting

Given an array arr of distinct integers. Rearrange the array in such a way that the first element is the largest and the second element is the smallest, the third element is the second largest and the fourth element is the second smallest, and so on.

Examples:

Input: arr[] = [7, 1, 2, 3, 4, 5, 6]
Output: [7, 1, 6, 2, 5, 3, 4]
Explanation: The first element is first maximum and second element is first minimum and so on.

Input: arr[] = [1, 6, 9, 4, 3, 7, 8, 2]
Output: [9, 1, 8, 2, 7, 3, 6, 4]
Explanation: The first element is first maximum and second element is first minimum and so on.

Expected Time Complexity: O(nlogn).
Expected Auxiliary Space: O(n).

Constraints:
1 ≤ arr.size() ≤ 10⁵
1 ≤ arr[i] ≤ 10⁵

Approach 01:

class Solution {
public:
    vector<int> alternateSort(vector<int>& arr) {
        // Sort the array in ascending order
        sort(arr.begin(), arr.end());

        // Split the array into two halves
        int midIndex = arr.size() / 2;
        vector<int> firstHalf(arr.begin(), arr.begin() + midIndex);
        vector<int> secondHalf(arr.begin() + midIndex, arr.end());

        // Sort the second half in descending order
        sort(secondHalf.rbegin(), secondHalf.rend());

        // Initialize an empty vector for the alternating sorted output
        vector<int> alternateArray;

        // Set minimum and maximum sizes for both halves
        int minSize = min(firstHalf.size(), secondHalf.size());
        int maxSize = max(firstHalf.size(), secondHalf.size());

        // Alternately append elements from secondHalf and firstHalf
        int i = 0;
        while (i < minSize) {
            alternateArray.push_back(secondHalf[i]);
            alternateArray.push_back(firstHalf[i]);
            i++;
        }

        // Append remaining elements if firstHalf is larger
        if (firstHalf.size() >= secondHalf.size()) {
            while (i < maxSize) {
                alternateArray.push_back(firstHalf[i]);
                i++;
            }
        } else {
            // Append remaining elements if secondHalf is larger
            while (i < maxSize) {
                alternateArray.push_back(secondHalf[i]);
                i++;
            }
        }

        return alternateArray;
    }
};

class Solution:
    def alternateSort(self,arr):
        # Sort the array in ascending order
        arr.sort()

        # Split the array into two halves
        midIndex = len(arr) // 2
        firstHalf = arr[:midIndex]
        secondHalf = arr[midIndex:]

        # Initialize an empty list for the alternating sorted output
        alternateArray = []

        # Sort the second half in descending order
        secondHalf.sort(reverse=True)

        # Set minimum and maximum sizes for both halves
        minSize = min(len(firstHalf), len(secondHalf))
        maxSize = max(len(firstHalf), len(secondHalf))

        # Alternately append elements from secondHalf and firstHalf
        i = 0
        while i < minSize:
            alternateArray.append(secondHalf[i])
            alternateArray.append(firstHalf[i])
            i += 1

        # Append remaining elements if firstHalf is larger
        if len(firstHalf) >= len(secondHalf):
            while i < maxSize:
                alternateArray.append(firstHalf[i])
                i += 1
        else:
            # Append remaining elements if secondHalf is larger
            while i < maxSize:
                alternateArray.append(secondHalf[i])
                i += 1

        return alternateArray

Time Complexity

• Sorting:

  The array is first sorted in ascending order, which takes \(O(n \log n)\), where n is the number of elements in the array. Additionally, sorting the second half in descending order also takes \(O(n \log n)\), but since these steps occur sequentially, the dominant time complexity is \(O(n \log n)\).

• Splitting:

  The array is split into two halves, which takes \(O(n)\) since each element is copied into two new vectors.

• Alternating Append:

  Alternating between the two halves and appending to the result array takes \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is dominated by the sorting step, which is \(O(n \log n)\).

Space Complexity

• Auxiliary Space for New Vectors:

  The algorithm creates two additional vectors, firstHalf and secondHalf, each storing approximately half of the elements from the original array. This takes \(O(n)\) extra space.

• Result Vector:

  The alternateArray also stores all n elements, which requires \(O(n)\) space.

• Overall Space Complexity:

  The space complexity is \(O(n)\) due to the creation of the extra vectors.