06. Maximum Sum Combination
✅ GFG solution to the Maximum Sum Combination problem: find top k maximum sum pairs from two arrays using priority queue and greedy approach. 🚀
The problem can be found at the following link: 🔗 Question Link
🧩 Problem Description
You are given two integer arrays a[] and b[] of equal size. A sum combination is formed by adding one element from a[] and one from b[], using each index pair (i, j) at most once. Your task is to return the top k maximum sum combinations, sorted in non-increasing order.
The goal is to efficiently find the k largest possible sums without generating all n² combinations, which would be inefficient for large arrays.
📘 Examples
Example 1
Input: a[] = [3, 2], b[] = [1, 4], k = 2
Output: [7, 6]
Explanation: Possible sums: 3 + 1 = 4, 3 + 4 = 7, 2 + 1 = 3, 2 + 4 = 6
Top 2 sums are 7 and 6.Example 2
Input: a[] = [1, 4, 2, 3], b[] = [2, 5, 1, 6], k = 3
Output: [10, 9, 9]
Explanation: The top 3 maximum possible sums are: 4 + 6 = 10, 3 + 6 = 9, and 4 + 5 = 9🔒 Constraints
$1 \le a.size() = b.size() \le 10^5$
$1 \le k \le a.size()$
$1 \le a[i], b[i] \le 10^4$
✅ My Approach
The optimal approach uses a Priority Queue (Max-Heap) combined with a Greedy Strategy and Visited Set to efficiently find the k largest sums without generating all combinations:
Max-Heap + Greedy + Visited Tracking
Sort Both Arrays:
Sort both arrays in descending order to start with the largest possible elements.
This ensures we begin with the maximum possible sum:
a[0] + b[0].
Initialize Data Structures:
Use a max-heap (priority queue) to always get the largest available sum.
Use a visited set to track already processed index pairs to avoid duplicates.
Store tuples of
(sum, index_i, index_j)in the heap.
Start with Maximum Sum:
Push the largest possible sum
a[0] + b[0]with indices(0, 0)into the heap.Mark
(0, 0)as visited.
Greedy Selection:
For each iteration (k times):
Pop the maximum sum from the heap and add it to the result.
From the current position
(i, j), explore two adjacent possibilities:(i+1, j): Next element from arrayawith same element from arrayb(i, j+1): Same element from arrayawith next element from arrayb
Add these new combinations to the heap if not already visited.
Avoid Duplicates:
Use a visited set with unique pair encoding to prevent processing the same combination twice.
This ensures each index pair is used at most once.
Continue Until k Results:
Repeat until we have collected k maximum sums.
📝 Time and Auxiliary Space Complexity
Expected Time Complexity: O(n log n + k log k), where n is the size of the arrays. The sorting takes O(n log n) time, and we perform k heap operations, each taking O(log k) time in the worst case.
Expected Auxiliary Space Complexity: O(k), where k is the number of elements we need to find. We use a heap of size at most k and a visited set that stores at most k unique pairs.
🧑💻 Code (C++)
class Solution {
public:
vector<int> topKSumPairs(vector<int>& a, vector<int>& b, int k) {
int n = a.size();
sort(a.begin(), a.end(), greater<>());
sort(b.begin(), b.end(), greater<>());
priority_queue<tuple<int, int, int>> pq;
unordered_set<long long> vis;
pq.emplace(a[0] + b[0], 0, 0);
vis.insert(0);
vector<int> res;
while (res.size() < k) {
int sum = get<0>(pq.top());
int i = get<1>(pq.top());
int j = get<2>(pq.top());
pq.pop();
res.push_back(sum);
if (i + 1 < n && vis.insert((long long)(i + 1) * n + j).second)
pq.emplace(a[i + 1] + b[j], i + 1, j);
if (j + 1 < n && vis.insert((long long)i * n + j + 1).second)
pq.emplace(a[i] + b[j + 1], i, j + 1);
}
return res;
}
};🧑💻 Code (Java)
class Solution {
public ArrayList<Integer> topKSumPairs(int[] a, int[] b, int k) {
int n = a.length;
Arrays.sort(a); Arrays.sort(b);
PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> y[0] - x[0]);
Set<String> vis = new HashSet<>();
pq.add(new int[]{a[n - 1] + b[n - 1], n - 1, n - 1});
vis.add((n - 1) + "#" + (n - 1));
ArrayList<Integer> res = new ArrayList<>();
while (res.size() < k) {
int[] top = pq.poll();
res.add(top[0]);
int i = top[1], j = top[2];
if (i > 0 && vis.add((i - 1) + "#" + j))
pq.add(new int[]{a[i - 1] + b[j], i - 1, j});
if (j > 0 && vis.add(i + "#" + (j - 1)))
pq.add(new int[]{a[i] + b[j - 1], i, j - 1});
}
return res;
}
}🐍 Code (Python)
class Solution:
def topKSumPairs(self, a, b, k):
n = len(a)
a.sort()
b.sort()
pq = [(-(a[-1] + b[-1]), n - 1, n - 1)]
vis = {(n - 1, n - 1)}
res = []
while len(res) < k:
s, i, j = heapq.heappop(pq)
res.append(-s)
if i > 0 and (i - 1, j) not in vis:
vis.add((i - 1, j))
heapq.heappush(pq, (-(a[i - 1] + b[j]), i - 1, j))
if j > 0 and (i, j - 1) not in vis:
vis.add((i, j - 1))
heapq.heappush(pq, (-(a[i] + b[j - 1]), i, j - 1))
return res🧠 Contribution and Support
For discussions, questions, or doubts related to this solution, feel free to connect on LinkedIn: 📬 Any Questions?. Let's make this learning journey more collaborative!
⭐ If you find this helpful, please give this repository a star! ⭐
📍Visitor Count
Last updated