Solution

Approach #1 Brute Force [Time Limit Exceeded]

Algorithm

The simplest solution is to consider every possible set of pairings possible by using the elements of the $$nums$$ array. For generating all the possible pairings, we make use of a function permute(nums, current_index). This function creates all the possible permutations of the elements of the given array.

To do so, permute takes the index of the current element $$current_index$$ as one of the arguments. Then, it swaps the current element with every other element in the array, lying towards its right, so as to generate a new ordering of the array elements. After the swapping has been done, it makes another call to permute but this time with the index of the next element in the array. While returning back, we reverse the swapping done in the current function call.

Thus, when we reach the end of the array, a new ordering of the array's elements is generated. We consider the elements to be taken for the pairings such that the first element of every pair comes from the first half of the new array and the second element comes from the last half of the array. Thus, we sum up the minimum elements out of all these possible pairings and find out the maximum sum out of them.

The animation below depicts the ways the permutations are generated.

!?!../Documents/561_Array.json:1000,563!?!

Complexity Analysis

• Time complexity : $$O(n!)$$ . A total of $$n!$$ permutations are possible for $$n$$ elements in the array.
• Space complexity : $$O(1)$$ . Constant extra space is used.

Approach #2 Using Sorting [Accepted]

Algorithm

In order to understand this approach, let us look at the problem from a different perspective. We need to form the pairings of the array's elements such that the overall sum of the minimum out of such pairings is maximum. Thus, we can look at the operation of choosing the minimum out of the pairing, say $$(a, b)$$ as incurring a loss of $$a - b$$ (if $$a> b$$ ), in the maximum sum possible.

The total sum will now be maximum if the overall loss incurred from such pairings is minimized. This minimization of loss in every pairing is possible only if the numbers chosen for the pairings lie closer to each other than to the other elements of the array.

Taking this into consideration, we can sort the elements of the given array and form the pairings of the elements directly in the sorted order. This will lead to the pairings of elements with minimum difference between them leading to the maximization of the required sum.

Complexity Analysis

• Time complexity : $$O\big(nlog(n)\big)$$ . Sorting takes $$O\big(nlog(n)\big)$$ time. We iterate over the array only once.

• Space complexity : $$O(1)$$ . Constant extra space is used.

Approach #3 Using Extra Array [Accepted]

Algorithm

This approach is somewhat related to the sorting approach. Since the range of elements in the given array is limited, we can make use of a hashmap $$arr$$ , such that $$arr[i]$$ stores the frequency of occurence of $$(i-10000)^{th}$$ element. This subtraction is done so as to be able to map the numbers in the range $$-10000 ≤ i ≤ -1$$ onto the hashmap.

Thus, now instead of sorting the array's elements, we can directly traverse the hashmap in an ascending order. But, any element could also occur multiple times in the given array. We need to take this factor into account.

For this, consider an example: nums: [a, b, a, b, b, a]. The sorted order of this array will be nums_sorted: [a, a, a, b, b, b]. (We aren't actually sorting the array in this approach, but the sorted array is taken just for demonstration). From the previous approach, we know that the required set of pairings is $$(a,a), (a,b), (b,b)$$ . Now, we can see that while choosing the minimum elements, $$a$$ will be chosen twice and $$b$$ will be chosen once only. This happens because the number of $$a$$ 's to be chosen has already been determined by the frequency of $$a$$ , leaving the rest of the places to be filled by $$b$$ . This is because, for the correct result we need to consider the elements in the ascending order. Thus, the lower number always gets priority to be added to the end result.

But, if the sorted elements take the form: nums_sorted: [a, a, b, b, b, b], the correct pairing will be $$(a,a), (b,b), (b,b)$$ . Again, in this case the number of $$a$$ 's chosen is already predetermined, but since the number of $$a$$ 's is odd, it doesn't impact the choice of $$b$$ in the final sum.

Thus, based on the above discussion, we traverse the hashmap $$arr$$ . If the current element is occuring $$freq_i$$ number of times, and one of the elements is left to be paired with other elements in the right region(considering a virtual sorted array), we consider the current element $$\left \lceil\frac{freq_i}{2}\right \rceil$$ number of times and the next element occuring in the array $$\left \lfloor\frac{freq_j}{2}\right \rfloor$$ number of times for the final sum. To propagate the impact of this left over chosen number, we make use of a flag $$d$$ . This flag is set to 1 if there is a leftover element from the current set which will be considered one more time. The same extra element already considered is taken into account while choosing an element from the next set.

While traversing the hashmap, we determine the correct number of times each element needs to be considered as discussed above. Note that the flag $$d$$ and the $$sum$$ remains unchanged if the current element of the hashmap doesn't exist in the array.

Below code is inspired by @fallcreek

Complexity Analysis

• Time complexity : $$O(n)$$ . The whole hashmap $$arr$$ of size $$n$$ is traversed only once.

• Space complexity : $$O(n)$$ . A hashmap $$arr$$ of size $$n$$ is used.

Analysis written by: @vinod23