Maximum difference between a group of k-elements and rest of the array

Introduction

For this current problem, we are given an array of elements and a value k. We need to find the maximum difference between a group of k-elements and the rest of the array for the given array. We need to first divide the array into two groups such that one group must contain k-elements and the other group must contain the rest of the array elements. The idea here is to select the best k-element group elements such that the maximum difference between this group and the group of remaining elements must be high.

Also see,  Rabin Karp Algorithm

Solution

Approach

Let’s have some simple examples to understand this problem. 

Example1: 

Say, we are provided with an array of elements as a = [1,3,2,4,6,5], k = 2.

Then we can divide the array as g1 = [1,2] and g2 = [3,4,5,6]. Thus we get the maximum difference between these two groups will be abs(sum(g2) - sum(g1)) = 18-3, i.e15. Here the main problem is to select the best possible elements for the k-element group.

Example2:

Say, we are provided with an array of elements as a = [1, -2, -3, -1, 3], k = 2.

Then we can divide the array as g1 = [-1, -2, -3] and g2 = [1, 3]. Thus we get the maximum difference between these two groups will be abs(sum(g2) - sum(g1)) = 4- (-6), i.e 10. The main problem is selecting the best possible elements for the k-element group.

Here we can observe mainly two cases to get the optimal solution. In the first case, we can group all the k-smallest elements and the rest of the elements as another group. Similarly, in the second case, we can group all the k-largest elements and the rest of the elements as another group. So sorting the array might help us to solve the problem easily.

In this problem, we just need to print the maximum difference and not the groups. So we can follow the below algorithm:

Step1: Sort the given array.

Step2: Calculate the sum of the whole array of elements.

Step3: As discussed, find the sum of the first k-smallest elements.

Step4: calculate the difference as d1 = abs( arraySum - 2*k_Smallest_sum)

Step5: Another case, find the sum of first k-largest elements.

Step6:   calculate the new difference as d2 = abs( arraySum - 2*k_largest_sum)

Step7: Finally, display the max(d1, d2) as output.

Code

Python:

def calculate_sum(arr, n):          #Calculating the sum of the given array up to n elements.
    sum = 0
    for i in range(n):
        sum = sum + arr[i]
    return sum

def solution(arr, k):

    #Step1: Sorting the array

    arr.sort()

    #Step2: calculating the whole array sum

    arr_total_sum = calculate_sum(arr, len(arr))

    #Step3:  find the sum of the first k-smallest elements.

    K_smallest = calculate_sum(arr, k)

    #Step4: calculate the difference as d1

    d1 = abs( arr_total_sum - 2*K_smallest)

   #Step5: find the sum of first k-largest elements.

    K_largest = calculate_sum(arr[-k:], k)

    #Step6: calculate the new difference as d2

    d2 = abs( arraySum - 2*K_largest)

    #Step7: Finally, display the max(d1, d2) as output.

    return max(d1, d2)

arr =  [1,3,2,4,6,5]
k = 2
print(solution(arr, k) 

You can also try this code with Online Python Compiler

Run Code

Output: 15

The time complexity for this python solution code is O(n).

You can find this solution in different languages by referring to this GFG blog.