Maximum possible difference of two subsets of an array

Difficulty Level Hard
Frequently asked in Atlassian Cadence India Directi FreeCharge Opera PayU Snapchat Times Internet Xome
Array Hash SortingViews 4733

Suppose, we have an integer array. The problem statement “Maximum possible difference of two subsets of an array” asks to find out the maximum possible difference between the two subsets of an array.

Conditions to be followed:

  • An array can contain repeating elements, but the highest frequency of an element should not be greater than 2.
  • You should make two subsets so that the difference between the sum of their respective elements is maximum.
  • All the elements of the array should be divided between the two subsets without leaving any element behind.
  • Two elements should not be the same within a subset.

Example

Maximum possible difference of two subsets of an array

arr[] = {2, 5, -3, -1, 5, 7}
13

Explanation

Subset → (2, 7, 5)- (-3, -1, 5) = 13

{1, 5, 3, -1, -5, 6}
21

Explanation

Subset → (1, 3, 5, 6) – (-5, -1) = 21

Algorithm

  1. Declare two Maps, one for positive and one for the negative element.
  2. Store the positive elements and their count in one map.
  3. Keep adding up all the positive elements that have frequency 1 and storing it in subset1.
  4. Store the negative element and its count in another map.
  5. Keep adding up all the negative elements that have frequency 1 and storing it in subset2.
  6. Return subset1-subset2.

Explanation

We have given an array, we need to find out the difference between the sum of the elements of two subsets and that should be maximum. We are going to use a Map. Hashing provides an efficient way to solve this question. We are going to use two Maps. One is for done operations on positive elements and another for on the negative elements. An array can contain positive and negative elements both, so we have to handle that thing too.

We will take an array and map. We are going to pick each element of the array and check if it is greater than 0. Then we are going to store it in the map with its number of occurrences. After storing the frequencies of the positive elements we are going to add up all the values of an array which are greater than 0 and also have a frequency of only 1, means we need to ignore those elements that come several times or more than once.

The same thing will be done with negative elements we will pick every element of an array and this time we will check if it is less than 0. We are going to store it in the map (making it a positive number) with its number of occurrences. After storing frequencies of the negative elements, we are going to add up all the values of an array which are less than 0 and also that have a frequency of only 1. Here also, we need to ignore those elements that come several times or more than once.

After getting the sum of all positive and negative elements condition followed that elements having frequency 1 only, we need to return the difference of both the sums and that would be our answer.

Code

C++ code to find Maximum possible difference of two subsets of an array

#include<iostream>
#include<unordered_map>

using namespace std;

int maxDiff(int arr[], int n)
{
    unordered_map<int, int> positiveElement;
    unordered_map<int, int> negativeElement;

    int sumSubset1 = 0, sumSubset2 = 0;
    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0)
            positiveElement[arr[i]]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] > 0 && positiveElement[arr[i]] == 1)
            sumSubset1 += arr[i];

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0)
            negativeElement[abs(arr[i])]++;

    for (int i = 0; i <= n - 1; i++)
        if (arr[i] < 0 &&
                negativeElement[abs(arr[i])] == 1)
            sumSubset2 += arr[i];

    return abs(sumSubset1 - sumSubset2);
}
int main()
{
    int arr[] = {2,5,-3,-1,5,7};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout << "Maximum difference found is: " << maxDiff(arr, n);
    return 0;
}

Maximum difference found is: 13

Java code to find Maximum possible difference of two subsets of an array

import java.util.HashMap;
class SubsetDifference
{
    public static int getDifference(int arr[], int n)
    {
        HashMap<Integer, Integer> positiveElement=new HashMap<Integer, Integer>();
        HashMap<Integer, Integer> negativeElement=new HashMap<Integer, Integer>();
        int sumSubset1 = 0, sumSubset2 = 0;
        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] > 0)
            {
                if(positiveElement.containsKey(arr[i]))
                    positiveElement.put(arr[i],positiveElement.get(arr[i])+1);
                else
                    positiveElement.put(arr[i],1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] > 0 && positiveElement.get(arr[i]) == 1)
                sumSubset1 += arr[i];

        for (int i = 0; i <= n - 1; i++)
        {
            if (arr[i] < 0)
            {
                if(negativeElement.containsKey(Math.abs(arr[i])))
                    negativeElement.put(Math.abs(arr[i]),negativeElement.get(Math.abs(arr[i]))+1);
                else
                    negativeElement.put(Math.abs(arr[i]),1);
            }
        }
        for (int i = 0; i <= n - 1; i++)
            if (arr[i] < 0 && negativeElement.get(Math.abs(arr[i]))== 1)
                sumSubset2 += arr[i];

        return Math.abs(sumSubset1 - sumSubset2);
    }
    public static void main(String [] args)
    {
        int arr[] = {2,5,-3,-1,5,7};
        int n = arr.length;
        System.out.println("Maximum difference found is:"+getDifference(arr, n));
    }
}

Maximum difference found is:13

Complexity Analysis

Time Complexity

O(n) where “n” is the number of elements in the array. Because we have used HashMap we are able to perform insertion/deletion/searching in O(1).

Space Complexity

O(n) where “n” is the number of elements in the array.

Translate »