Given an array of even number of elements, form groups of 2 using these array elements such that the difference between the group with highest sum and the one with lowest sum is maximum.
Note: An element can be a part of one group only and it has to be a part of at least 1 group.
Examples:
Input : arr[] = {1, 4, 9, 6}
Output : 10
Groups formed will be (1, 4) and (6, 9),
the difference between highest sum group
(6, 9) i.e 15 and lowest sum group (1, 4)
i.e 5 is 10.
Input : arr[] = {6, 7, 1, 11}
Output : 11
Groups formed will be (1, 6) and (7, 11),
the difference between highest sum group
(7, 11) i.e 18 and lowest sum group (1, 6)
i.e 7 is 11.
Simple Approach: We can solve this problem by making all possible combinations and checking each set of combination differences between the group with the highest sum and with the lowest sum. A total of n*(n-1)/2 such groups would be formed (nC2).
Time Complexity: O(n^3), because it will take O(n^2) to generate groups and to check against each group n iterations will be needed thus overall it takes O(n^3) time.
Efficient Approach: We can use the greedy approach. Sort the whole array and our result is sum of last two elements minus sum of first two elements.
Python3
# Python 3 program to find minimum difference # between groups of highest and lowest def CalculateMax(arr, n): # Sorting the whole array. arr.sort() min_sum = arr[0] + arr[1] max_sum = arr[n - 1] + arr[n - 2] return abs(max_sum - min_sum)# Driver codearr = [6, 7, 1, 11]n = len(arr)print(CalculateMax(arr, n))# This code is contributed# by Shrikant13 |
11
Time Complexity: O (n * log n)
Space Complexity: O(1) as no extra space has been taken.
Further Optimization :
Instead of sorting, we can find a maximum two and minimum of two in linear time and reduce the time complexity to O(n).
Python3
# Python Program for Maximum # difference between groups # of size two# import the moduleimport sysdef CalculateMax(arr,n): first_min=sys.maxsize second_min=sys.maxsize for i in range(n): # If current element is smaller than first_min # then update both first_min and second_min if(arr[i]<first_min): second_min=first_min first_min = arr[i] # If arr[i] is in between first and second # then update second elif(arr[i]<second_min and arr[i]!=first_min): second_min=arr[i] first_max=-1*sys.maxsize second_max=-1*sys.maxsize for i in range(n): # If current element is greater than first_max # then update both first and second if(arr[i]>first_max): second_max=first_max first_max = arr[i] # If arr[i] is in between first_max and # second_max then update second elif(arr[i]>second_max and arr[i]!=first_max): second_max=arr[i] return abs(first_max+second_max-first_min-second_min)# Driver codearr = [ 6, 7, 1, 11 ];n = len(arr)print(CalculateMax(arr, n))# This code is contributed by Pushpesh Raj |
11
Time Complexity: O(N)
Auxiliary Space: O(1)
Please refer complete article on Maximum difference between groups of size two for more details!
You’ll access excellent video content by our CEO, Sandeep Jain, tackle common interview questions, and engage in real-time coding contests covering various DSA topics. We’re here to prepare you thoroughly for online assessments and interviews.
Ready to dive in? Explore our free demo content and join our DSA course, trusted by over 100,000neveropen! Whether it’s DSA in C++, Java, Python, or JavaScript we’ve got you covered. Let’s embark on this exciting journey together!
