Swap and Maximize

Given an array arr[ ] of positive elements. Consider the array as a circular array, meaning the element after the last element is the first element of the array. The task is to find the maximum sum of the absolute differences between consecutive elements with shuffling of array elements allowed i.e. shuffle the array elements and make [a₁..a_n] such order that |a₁ – a₂| + |a₂ – a₃| + …… + |a_n-1 – a_n| + |a_n – a₁| is maximized.

Examples:

Input: arr[] = [4, 2, 1, 8]
Output: 18
Explanation: After Shuffling, we get [1, 8, 2, 4]. Sum of absolute difference between consecutive elements after rearrangement = |1 - 8| + |8 - 2| + |2 - 4| + |4 - 1| = 7 + 6 + 2 + 3 = 18.

Input: arr[] = [10, 12]
Output: 4
Explanation: No need of rearrangement. Sum of absolute difference between consecutive elements = |10 - 12| + |12 - 10| = 2 + 2 = 4.

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

Approach 01:

class Solution {
public:
    long long maxSum(vector<int>& numbers) {
        sort(numbers.begin(), numbers.end());
        long long leftPointer = 0;
        long long rightPointer = numbers.size() - 1;
        vector<long long> reorderedList;
        
        // Rearrange the array
        while (leftPointer <= rightPointer) {
            if (leftPointer == rightPointer) {
                reorderedList.push_back(numbers[leftPointer]);
            } else {
                reorderedList.push_back(numbers[leftPointer]);
                reorderedList.push_back(numbers[rightPointer]);
            }
            leftPointer++;
            rightPointer--;
        }
        
        long long totalSum = 0;
        long long listLength = reorderedList.size();

        // Calculate the maximum sum
        if (listLength == 2) {
            return abs(reorderedList[0] - reorderedList[1]) * 2;
        } else {
            for (int i = 0; i < listLength - 1; ++i) {
                totalSum += abs(reorderedList[i] - reorderedList[i + 1]);
            }
            long long edgeDifference = abs(reorderedList[listLength - 1] - reorderedList[0]);
            long long maxSumValue = edgeDifference + totalSum;
            return maxSumValue;
        }
    }
};

class Solution:
    def maxSum(self, numbers):
        numbers.sort()
        leftPointer = 0
        rightPointer = len(numbers) - 1
        reorderedList = []
        
        # Rearrange the array
        while leftPointer <= rightPointer:
            if leftPointer == rightPointer:
                reorderedList.append(numbers[leftPointer])
            else:
                reorderedList.append(numbers[leftPointer])
                reorderedList.append(numbers[rightPointer])
            leftPointer += 1
            rightPointer -= 1
        
        totalSum = 0
        listLength = len(reorderedList)
        
        # Calculate the maximum sum
        if listLength == 2:
            return abs(reorderedList[0] - reorderedList[1]) * 2
        else:
            for i in range(listLength - 1):
                totalSum += abs(reorderedList[i] - reorderedList[i + 1])
            edgeDifference = abs(reorderedList[listLength - 1] - reorderedList[0])
            maxSumValue = edgeDifference + totalSum
            return maxSumValue

Time Complexity

• Sorting:

  Sorting the numbers array takes \(O(N \log N)\), where \(N\) is the number of elements in numbers.

• Rearranging the Array:

  The while loop that rearranges elements runs \(O(N)\) times, as each element is accessed once. This operation is therefore \(O(N)\).

• Calculating the Maximum Sum:

  The for loop that calculates the sum of absolute differences between adjacent elements also iterates \(O(N)\) times, making this step \(O(N)\).

• Overall Time Complexity:

  The total time complexity is dominated by the sorting step, resulting in \(O(N \log N)\).

Space Complexity

• Auxiliary Storage for reorderedList:

  The vector reorderedList stores \(N\) elements, giving it a space complexity of \(O(N)\).

• Overall Space Complexity:

  The total space complexity is \(O(N)\) due to the additional storage used by reorderedList.