K maximum sum combinations from two arrays

Last Updated : 10 Jul, 2023

Given two equally sized arrays (A, B) and N (size of both arrays).
A sum combination is made by adding one element from array A and another element of array B. Display the maximum K valid sum combinations from all the possible sum combinations.

Examples:

Input :  A[] : {3, 2} 
         B[] : {1, 4}
         K : 2 [Number of maximum sum
               combinations to be printed]
Output : 7    // (A : 3) + (B : 4)
         6    // (A : 2) + (B : 4)
Input :  A[] : {4, 2, 5, 1}
         B[] : {8, 0, 3, 5}
         K : 3
Output : 13   // (A : 5) + (B : 8)
         12   // (A : 4) + (B :  8)
         10   // (A : 2) + (B : 8)

Approach 1 (Naive Algorithm): We can use Brute force through all the possible combinations that can be made by taking one element from array A and another from array B and inserting them to a max heap. In a max heap maximum element is at the root node so whenever we pop from max heap we get the maximum element present in the heap. After inserting all the sum combinations we take out K elements from max heap and display it.

Below is the implementation of the above approach.

C++

// A simple C++ program to find N maximum
// combinations from two arrays,
#include <bits/stdc++.h>
using namespace std;
 
// function to display first N maximum sum
// combinations
void KMaxCombinations(int A[], int B[], 
                      int N, int K)
{
    // max heap.
    priority_queue<int> pq;
 
    // insert all the possible combinations
    // in max heap.
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            pq.push(A[i] + B[j]);
 
    // pop first N elements from max heap
    // and display them.
    int count = 0;
    while (count < K) {
        cout << pq.top() << endl;
        pq.pop();
        count++;
    }
}
 
// Driver Code.
int main()
{
    int A[] = { 4, 2, 5, 1 };
    int B[] = { 8, 0, 5, 3 };
    int N = sizeof(A) / sizeof(A[0]);
    int K = 3;
   
    // Function call
    KMaxCombinations(A, B, N, K);
    return 0;
}

Java

// Java program to find K
// maximum combinations
// from two arrays,
import java.io.*;
import java.util.*;
 
class GFG {
 
    // function to display first K
    // maximum sum combinations
    static void KMaxCombinations(int A[], int B[], 
                                 int N, int K)
    {
        // max heap.
        PriorityQueue<Integer> pq
            = new PriorityQueue<Integer>(
                Collections.reverseOrder());
 
        // Insert all the possible
        // combinations in max heap.
        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                pq.add(A[i] + B[j]);
 
        // Pop first N elements
        // from max heap and
        // display them.
        int count = 0;
 
        while (count < K) {
            System.out.println(pq.peek());
            pq.remove();
            count++;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int A[] = { 4, 2, 5, 1 };
        int B[] = { 8, 0, 5, 3 };
        int N = A.length;
        int K = 3;
 
        // Function Call
        KMaxCombinations(A, B, N, K);
    }
}
 
// This code is contributed by Mayank Tyagi

Python 3

# Python program to find
# K maximum combinations
# from two arrays
import math
from queue import PriorityQueue
 
# Function to display first K
# maximum sum combinations
 
 
def KMaxCombinations(A, B, N, K):
 
    # Max heap.
    pq = PriorityQueue()
 
    # Insert all the possible
    # combinations in max heap.
    for i in range(0, N):
        for j in range(0, N):
            a = A[i] + B[j]
            pq.put((-a, a))
 
    # Pop first N elements from
    # max heap and display them.
    count = 0
    while (count < K):
        print(pq.get()[1])
        count = count + 1
 
 
# Driver method
A = [4, 2, 5, 1]
B = [8, 0, 5, 3]
N = len(A)
K = 3
 
# Function call
KMaxCombinations(A, B, N, K)
 
# This code is contributed
# by Gitanjali.

C#

// C# program to find K
// maximum combinations
// from two arrays,
using System;
using System.Collections.Generic;
public class GFG
{
 
  // function to display first K
  // maximum sum combinations
  static void KMaxCombinations(int []A, int []B, 
                               int N, int K)
  {
 
    // max heap.
    List<int> pq
      = new List<int>();
 
    // Insert all the possible
    // combinations in max heap.
    for (int i = 0; i < N; i++)
      for (int j = 0; j < N; j++)
        pq.Add(A[i] + B[j]);
 
    // Pop first N elements
    // from max heap and
    // display them.
    int count = 0;
    pq.Sort();
    pq.Reverse();
    while (count < K)
    {
      Console.WriteLine(pq[0]);
      pq.RemoveAt(0);
      count++;
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
    int []A = { 4, 2, 5, 1 };
    int []B = { 8, 0, 5, 3 };
    int N = A.Length;
    int K = 3;
 
    // Function Call
    KMaxCombinations(A, B, N, K);
  }
}
 
// This code is contributed by Rajput-Ji 

Javascript

<script>
// Javascript program to find K
// maximum combinations
// from two arrays,
 
// function to display first K
// maximum sum combinations
function KMaxCombinations(A, B, N, K)
{
 
    // max heap.
    let pq = [];
 
    // Insert all the possible
    // combinations in max heap.
    for (let i = 0; i < N; i++)
    for (let j = 0; j < N; j++)
        pq.push(A[i] + B[j]);
 
    // Pop first N elements
    // from max heap and
    // display them.
    let count = 0;
    pq.sort((a, b) => a - b).reverse();
    while (count < K)
    {
    document.write(pq[0] + "<br>");
    pq.shift();
    count++;
    }
}
 
// Driver Code
    let A = [ 4, 2, 5, 1 ];
    let B = [ 8, 0, 5, 3 ];
    let N = A.length;
    let K = 3;
 
    // Function Call
    KMaxCombinations(A, B, N, K);
 
 
// This code is contributed by gfgking
</script>

Output

13
12
10

Time Complexity: O(N^2*log(N^2))
Auxiliary Space : O(N^2)

Approach 2 (Sorting, Max heap, Map) :

Instead of brute-forcing through all the possible sum combinations, we should find a way to limit our search space to possible candidate sum combinations.

Sort both arrays array A and array B.
Create a max heap i.e priority_queue in C++ to store the sum combinations along with the indices of elements from both arrays A and B which make up the sum. Heap is ordered by the sum.
Initialize the heap with the maximum possible sum combination i.e (A[N – 1] + B[N – 1] where N is the size of array) and with the indices of elements from both arrays (N – 1, N – 1). The tuple inside max heap will be (A[N-1] + B[N – 1], N – 1, N – 1). Heap is ordered by first value i.e sum of both elements.
Pop the heap to get the current largest sum and along with the indices of the element that make up the sum. Let the tuple be (sum, i, j).
1. Next insert (A[i – 1] + B[j], i – 1, j) and (A[i] + B[j – 1], i, j – 1) into the max heap but make sure that the pair of indices i.e (i – 1, j) and (i, j – 1) are not
  already present in the max heap. To check this we can use set in C++.
2. Go back to 4 until K times.

Below is the implementation of the above approach:

CPP

// An efficient C++ program to find top K elements
// from two arrays.
#include <bits/stdc++.h>
using namespace std;
 
// Function prints k maximum possible combinations
void KMaxCombinations(vector<int>& A, 
                      vector<int>& B, int K)
{
    // sort both arrays A and B
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
 
    int N = A.size();
 
    // Max heap which contains tuple of the format
    // (sum, (i, j)) i and j are the indices
    // of the elements from array A
    // and array B which make up the sum.
    priority_queue<pair<int, pair<int, int> > > pq;
 
    // my_set is used to store the indices of
    // the  pair(i, j) we use my_set to make sure
    // the indices does not repeat inside max heap.
    set<pair<int, int> > my_set;
 
    // initialize the heap with the maximum sum
    // combination ie (A[N - 1] + B[N - 1])
    // and also push indices (N - 1, N - 1) along
    // with sum.
    pq.push(make_pair(A[N - 1] + B[N - 1],
                      make_pair(N - 1, N - 1)));
 
    my_set.insert(make_pair(N - 1, N - 1));
 
    // iterate upto K
    for (int count = 0; count < K; count++)
    {
        // tuple format (sum, (i, j)).
        pair<int, pair<int, int> > temp = pq.top();
        pq.pop();
 
        cout << temp.first << endl;
 
        int i = temp.second.first;
        int j = temp.second.second;
 
        int sum = A[i - 1] + B[j];
 
        // insert (A[i - 1] + B[j], (i - 1, j))
        // into max heap.
        pair<int, int> temp1 = make_pair(i - 1, j);
 
        // insert only if the pair (i - 1, j) is
        // not already present inside the map i.e.
        // no repeating pair should be present inside
        // the heap.
        if (my_set.find(temp1) == my_set.end()) 
        {
            pq.push(make_pair(sum, temp1));
            my_set.insert(temp1);
        }
 
        // insert (A[i] + B[j - 1], (i, j - 1))
        // into max heap.
        sum = A[i] + B[j - 1];
        temp1 = make_pair(i, j - 1);
 
        // insert only if the pair (i, j - 1)
        // is not present inside the heap.
        if (my_set.find(temp1) == my_set.end())
        {
            pq.push(make_pair(sum, temp1));
            my_set.insert(temp1);
        }
    }
}
 
// Driver Code.
int main()
{
    vector<int> A = { 1, 4, 2, 3 };
    vector<int> B = { 2, 5, 1, 6 };
    int K = 4;
   
    // Function call
    KMaxCombinations(A, B, K);
    return 0;
}

Java

// An efficient Java program to find 
// top K elements from two arrays.
 
import java.io.*;
import java.util.*;
 
class GFG {
    public static void MaxPairSum(Integer[] A, 
                                  Integer[] B,
                                  int N, int K)
    {
        // sort both arrays A and B
        Arrays.sort(A);
        Arrays.sort(B);
         
        // Max heap which contains Pair of 
        // the format (sum, (i, j)) i and j are 
        // the indices of the elements from 
        // array A and array B which make up the sum.
        PriorityQueue<PairSum> sums
            = new PriorityQueue<PairSum>();
         
         // pairs is used to store the indices of
        // the  Pair(i, j) we use pairs to make sure
        // the indices does not repeat inside max heap.
        HashSet<Pair> pairs = new HashSet<Pair>();
         
        // initialize the heap with the maximum sum
        // combination ie (A[N - 1] + B[N - 1])
        // and also push indices (N - 1, N - 1) along
        // with sum.
        int l = N - 1;
        int m = N - 1;
        pairs.add(new Pair(l, m));
        sums.add(new PairSum(A[l] + B[m], l, m));
         
        // iterate upto K
        for (int i = 0; i < K; i++) 
        {
            // Poll the element from the 
            // maxheap in theformat (sum, (l,m))
            PairSum max = sums.poll();
            System.out.println(max.sum);
            l = max.l - 1;
            m = max.m;
            // insert only if l and m are greater 
            // than 0 and the pair (l, m) is
            // not already present inside set i.e.
            // no repeating pair should be 
            // present inside the heap.
            if (l >= 0 && m >= 0
                && !pairs.contains(new Pair(l, m))) 
            {
                // insert (A[l]+B[m], (l, m)) 
                // in the heap
                sums.add(new PairSum(A[l] 
                         + B[m], l, m));
                pairs.add(new Pair(l, m));
            }
 
            l = max.l;
            m = max.m - 1;
 
            // insert only if l and m are 
            // greater than 0 and
            // the pair (l, m) is not 
            // already present inside
            // set i.e. no repeating pair 
            // should be present
            // inside the heap.
            if (l >= 0 && m >= 0
                && !pairs.contains(new Pair(l, m))) 
            {
                // insert (A[i1]+B[i2], (i1, i2)) 
                // in the heap
                sums.add(new PairSum(A[l] 
                         + B[m], l, m));
                pairs.add(new Pair(l, m));
            }
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        Integer A[] = { 1, 4, 2, 3 };
        Integer B[] = { 2, 5, 1, 6 };
        int N = A.length;
        int K = 4;
 
        // Function Call
        MaxPairSum(A, B, N, K);
    }
 
    public static class Pair {
 
        public Pair(int l, int m)
        {
            this.l = l;
            this.m = m;
        }
 
        int l;
        int m;
 
        @Override public boolean equals(Object o)
        {
            if (o == null) {
                return false;
            }
            if (!(o instanceof Pair)) {
                return false;
            }
            Pair obj = (Pair)o;
            return (l == obj.l && m == obj.m);
        }
 
        @Override public int hashCode()
        {
            return Objects.hash(l, m);
        }
    }
 
    public static class PairSum
        implements Comparable<PairSum> {
 
        public PairSum(int sum, int l, int m)
        {
            this.sum = sum;
            this.l = l;
            this.m = m;
        }
 
        int sum;
        int l;
        int m;
 
        @Override public int compareTo(PairSum o)
        {
            return Integer.compare(o.sum, sum);
        }
    }
}

Python3

import heapq
 
# Function prints k maximum possible combinations
def KMaxCombinations(a, b, k):
     
    # Sorting the arrays.
    a.sort()
    b.sort()
     
    n = len(a)
     
    # Using a max-heap.
    pq = []
    heapq.heapify(pq)
    pq.append((-a[n-1] - b[n-1], (n - 1, n - 1)))
     
    # Using a set.
    my_set = set() 
    my_set.add((n - 1, n - 1))
     
     
     
    for count in range(K):
         
        #  tuple format (sum, (i, j)).
        temp = heapq.heappop(pq)
         
        print(-temp[0])
         
        i = temp[1][0]
        j = temp[1][1]
        sum = a[i - 1] + b[j]
         
        temp1 = (i - 1, j)
         
        # insert (A[i - 1] + B[j], (i - 1, j))
        # into max heap.
         
        #  insert only if the pair (i - 1, j) is
        # not already present inside the map i.e.
        # no repeating pair should be present inside
        # the heap.
        if(temp1 not in my_set):
            heapq.heappush(pq, (-sum, temp1))
            my_set.add(temp1)
         
        sum = a[i] + b[j - 1]
         
        temp1 = (i, j - 1)
         
        # insert (A[i1] + B[j = 1], (i, j - 1))
        # into max heap.
         
        # insert only if the pair (i, j - 1)
        # is not present inside the heap.
        if(temp1 not in my_set):
            heapq.heappush(pq, (-sum, temp1))
            my_set.add(temp1)
 
 
 
# Driver Code.
A = [ 1, 4, 2, 3 ];
B = [ 2, 5, 1, 6 ];
K = 4;
   
# Function call
KMaxCombinations(A, B, K);
 
# This code is contributed by phasing17

C#

using System;
using System.Collections.Generic;
 
class GFG {
    static void KMaxCombinations(int[] a, int[] b, int k)
    {
        // Sorting the arrays.
        Array.Sort(a, (x, y) => x - y);
        Array.Sort(b, (x, y) => x - y);
 
        int n = a.Length;
 
        // Using a max-heap.
        var pq = new List<int[]>();
        pq.Add(new int[] { -a[n - 1] - b[n - 1], n - 1,
                           n - 1 });
        pq.Sort((x, y) => {
            if (x[0] == y[0])
                return x[1] - y[1];
            return x[0] - y[0];
        });
 
        // Using a set.
        var mySet = new HashSet<string>();
        mySet.Add($"{n - 1},{n - 1}");
 
        for (int count = 0; count < k; count++) {
            // tuple format (sum, (i, j)).
            var temp = pq[0];
            pq.RemoveAt(0);
 
            Console.WriteLine(-temp[0]);
 
            int i = temp[1];
            int j = temp[2];
            int sum = a[i - 1] + b[j];
 
            var temp1 = new int[] { i - 1, j };
 
            // insert (A[i - 1] + B[j], (i - 1, j)) into max
            // heap. insert only if the pair (i - 1, j) is
            // not already present inside the set.
            if (!mySet.Contains($"{temp1[0]},{temp1[1]}")) {
                pq.Add(
                    new int[] { -sum, temp1[0], temp1[1] });
                mySet.Add($"{temp1[0]},{temp1[1]}");
            }
 
            sum = a[i] + b[j - 1];
 
            temp1 = new int[] { i, j - 1 };
 
            // insert (A[i] + B[j - 1], (i, j - 1)) into max
            // heap. insert only if the pair (i, j - 1) is
            // not present inside the set.
            if (!mySet.Contains($"{temp1[0]},{temp1[1]}")) {
                pq.Add(
                    new int[] { -sum, temp1[0], temp1[1] });
                mySet.Add($"{temp1[0]},{temp1[1]}");
                pq.Sort((x, y) => {
                    if (x[0] == y[0])
                        return x[1] - y[1];
                    return x[0] - y[0];
                });
            }
        }
    }
 
    static void Main(string[] args)
    {
        // Driver Code.
        int[] A = { 1, 4, 2, 3 };
 
        int[] B = { 2, 5, 1, 6 };
 
        int K = 4;
 
        // Function call
        KMaxCombinations(A, B, K);
    }
}
 
// This code is contributed by phasing17

Javascript

function KMaxCombinations(a, b, k) {
  // Sorting the arrays.
  a.sort((a, b) => a - b);
  b.sort((a, b) => a - b);
 
  const n = a.length;
 
  // Using a max-heap.
  const pq = [];
  pq.push([-a[n - 1] - b[n - 1], [n - 1, n - 1]]);
  pq.sort(function(a, b)
  {
      if (a[0] == b[0])
        return a[1] - b[1];
        return a[0] - b[0];
  })
 
  // Using a set.
  const mySet = new Set();
  mySet.add([n - 1, n - 1]);
 
  for (let count = 0; count < k; count++) {
    // tuple format (sum, (i, j)).
    const temp = pq.shift();
 
    console.log(-temp[0]);
 
    const i = temp[1][0];
    const j = temp[1][1];
    let sum = a[i - 1] + b[j];
 
    let temp1 = [i - 1, j];
 
    // insert (A[i - 1] + B[j], (i - 1, j)) into max heap.
    // insert only if the pair (i - 1, j) is
    // not already present inside the set.
    if (!mySet.has(temp1.toString())) {
      pq.unshift([-sum, temp1]);
      mySet.add(temp1.toString());
    }
 
    sum = a[i] + b[j - 1];
 
    temp1 = [i, j - 1];
 
    // insert (A[i] + B[j - 1], (i, j - 1)) into max heap.
    // insert only if the pair (i, j - 1) is not present inside the set.
    if (!mySet.has(temp1.toString())) {
      pq.unshift([-sum, temp1]);
      mySet.add(temp1.toString());
       pq.sort(function(a, b)
  {
      if (a[0] == b[0])
        return a[1] - b[1];
        return a[0] - b[0];
  })
    }
  }
}
 
// Driver Code.
const A = [1, 4, 2, 3];
const B = [2, 5, 1, 6];
const K = 4;
 
// Function call
KMaxCombinations(A, B, K);
 
// This code is contributed by phasing17.

Output

Time Complexity : O(N log N) assuming K <= N
Auxiliary Space : O(N)

foreverrookie

Improve

Maximum distinct elements after removing k elements

Median of Stream of Running Integers using STL

Some other type of Heap

Easy problems on Heap

Medium problems on Heap

Hard problems on Heap

K maximum sum combinations from two arrays

C++

Java

Python 3

C#

Javascript

CPP

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?