Maximum difference between two subsets of m elements

Last Updated : 04 Mar, 2025

Given an array of n integers and a number m, find the maximum possible difference between two sets of m elements chosen from given array.

Examples:

Input : arr[] = 1 2 3 4 5
m = 4
Output : 4
The maximum four elements are 2, 3, 4 and 5. The minimum four elements are 1, 2, 3 and 4. The difference between two sums is (2 + 3 + 4 + 5) - (1 + 2 + 3 + 4) = 4

Input : arr[] = 5 8 11 40 15
m = 2
Output : 42
The difference is (40 + 15) - (5 + 8).

[Naive Solution] - Using Sorting - O(n Log n) Time and O(1) Space

The idea is to first sort the array, then find sum of first m elements and sum of last m elements. Finally return difference between two sums.

C++

#include <bits/stdc++.h>
using namespace std;

// utility function
int findDiff(vector<int>& arr, int m)
{
    int max = 0, min = 0;

    // sort array
    sort(arr.begin(), arr.end());
    
    // Traverse m elements from both ends
    int n = arr.size();
    for (int i = 0; i < m; i++) {
        min += arr[i];
        max += arr[n - 1 - i];
    }

    return (max - min);
}

// Driver code
int main()
{
    vector<int> arr = { 1, 2, 3, 4, 5 };
    int m = 4;
    cout << findDiff(arr, m);
    return 0;
}

Java

import java.util.Arrays;

public class Main {
    
    // utility function
    public static int findDiff(int[] arr, int m) {
        int max = 0, min = 0;

        // sort array
        Arrays.sort(arr);
        
        // Traverse m elements from both ends
        int n = arr.length;
        for (int i = 0;i < m; i++) {
            min += arr[i];
            max += arr[n - 1 - i];
        }

        return (max - min);
    }

    // Driver code
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int m = 4;
        System.out.println(findDiff(arr, m));
    }
}

Python

def find_diff(arr, m):
    max_sum = 0
    min_sum = 0

    # sort array
    arr.sort()
    
    # Traverse m elements from both ends
    n = len(arr)
    for i in range(m):
        min_sum += arr[i]
        max_sum += arr[n - 1 - i]

    return max_sum - min_sum

# Driver code
arr = [1, 2, 3, 4, 5]
m = 4
print(find_diff(arr, m))

using System;
using System.Collections.Generic;
using System.Linq;

class Program {
    // utility function
    static int FindDiff(List<int> arr, int m) {
        int max = 0, min = 0;

        // sort array
        arr.Sort();
        
        // Traverse m elements from both ends
        int n = arr.Count;
        for (int i = 0; i < m; i++) {
            min += arr[i];
            max += arr[n - 1 - i];
        }

        return max - min;
    }

    // Driver code
    static void Main() {
        List<int> arr = new List<int> { 1, 2, 3, 4, 5 };
        int m = 4;
        Console.WriteLine(FindDiff(arr, m));
    }
}

JavaScript

function findDiff(arr, m) {
    let max = 0, min = 0;

    // sort array
    arr.sort((a, b) => a - b);
    
    // Traverse m elements from both ends
    let n = arr.length;
    for (let i = 0; i < m; i++) {
        min += arr[i];
        max += arr[n - 1 - i];
    }

    return max - min;
}

// Driver code
let arr = [1, 2, 3, 4, 5];
let m = 4;
console.log(findDiff(arr, m));

Output

[Naive Solution] - Using Heap - O(n Log m) Time and O(m) Space

The idea is based on the solution discussed in k largest elements in an array

Create a Min Heap to Store m largest. We first push first m elements. For remaining n-m elements, we compare every element with the heap top. If Heap top is smaller, we insert the new element in the min heap
In the same way, create a Max Heap to Store m smallest.
Find the sums of elements in both the heaps and return the difference of two sums.

C++

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int findDiff(vector<int>& arr, int m) {
    
    // Min heap to store the 'm' largest elements
    priority_queue<int, vector<int>, greater<int>> mnH;
    
    // Max heap to store the 'm' smallest elements
    priority_queue<int> mxH;

    // Maintain 'm' smallest elements in mxH
    for (int x : arr) {
        mxH.push(x);
        if (mxH.size() > m) mxH.pop();
    }

    // Maintain 'm' largest elements in mnH
    for (int x : arr) {
        mnH.push(x);
        if (mnH.size() > m) mnH.pop();
    }

    // Compute sum of 'm' smallest and 'm' largest
    int minSum = 0, maxSum = 0;
    while (!mxH.empty()) minSum += mxH.top(), mxH.pop();
    while (!mnH.empty()) maxSum += mnH.top(), mnH.pop();

    return maxSum - minSum;
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    int m = 4;
    cout << findDiff(arr, m) << endl;
    return 0;
}

Java

import java.util.*;

class GfG {
    static int findDiff(int[] arr, int m) {
        
        // Min heap to store the 'm' largest elements
        PriorityQueue<Integer> mnH = new PriorityQueue<>();
        
        // Max heap to store the 'm' smallest elements
        PriorityQueue<Integer> mxH = new PriorityQueue<>(Collections.reverseOrder());

        // Maintain 'm' smallest elements in mxH
        for (int x : arr) {
            mxH.add(x);
            if (mxH.size() > m) mxH.poll();
        }

        // Maintain 'm' largest elements in mnH
        for (int x : arr) {
            mnH.add(x);
            if (mnH.size() > m) mnH.poll();
        }

        // Compute sum of 'm' smallest and 'm' largest
        int minSum = 0, maxSum = 0;
        while (!mxH.isEmpty()) minSum += mxH.poll();
        while (!mnH.isEmpty()) maxSum += mnH.poll();

        return maxSum - minSum;
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int m = 4;
        System.out.println(findDiff(arr, m));
    }
}

Python

# Function to find the difference between the sum of m largest and m smallest elements
import heapq

def find_diff(arr, m):
    
    # Min heap to store the 'm' largest elements
    mnH = []
    
    # Max heap to store the 'm' smallest elements
    mxH = []

    # Maintain 'm' smallest elements in mxH
    for x in arr:
        heapq.heappush(mxH, -x)
        if len(mxH) > m:
            heapq.heappop(mxH)

    # Maintain 'm' largest elements in mnH
    for x in arr:
        heapq.heappush(mnH, x)
        if len(mnH) > m:
            heapq.heappop(mnH)

    # Compute sum of 'm' smallest and 'm' largest
    min_sum = -sum(mxH)
    max_sum = sum(mnH)

    return max_sum - min_sum

arr = [1, 2, 3, 4, 5]
m = 4
print(find_diff(arr, m))

Output

Time Complexity: O(n * log m), this solution can work in O(m + (n-m) Log m) as build heap take linear time.

Merge Two Binary Max Heaps

TheGameOf256

Improve

Article Tags :

Practice Tags :

Maximum difference between two subsets of m elements

[Naive Solution] - Using Sorting - O(n Log n) Time and O(1) Space

[Naive Solution] - Using Heap - O(n Log m) Time and O(m) Space

Similar Reads

Some other type of Heap

Easy problems on Heap

Thank You!

What kind of Experience do you want to share?