Maximum Sum Combination Using Heap (Priority Queue) in C++ | Top K Pair Sums Explained

1. Problem Statement

In Simple Words: Imagine you have two separate decks of cards with numbers on them. You draw one card from the first deck and one card from the second deck, adding their values together to get a "sum combination." Your task is to find the highest possible sums you can make, specifically the top $C$ highest sums, in decreasing order.

Original Problem Statement:

Given two integer arrays $A$ and $B$ of size $N$ each, and an integer $C$ , find the top $C$ maximum sum combinations where a combination is defined as $A[i] + B[j]$ . Return the sums in descending order.

Input Format:

An integer array $A$ of size $N$ .
An integer array $B$ of size $N$ .
An integer $C$ representing the number of top sums required.

Output Format:

An integer array of size $C$ containing the top $C$ maximum sum combinations.

Constraints:

$1 \le N \le 10^5$
$1 \le C \le 10^5$
$1 \le A[i], B[i] \le 10^5$

2. Examples

Let's look at a few examples to understand how the combinations work.

Example 1

Input: A = [3, 2], B = [1, 4], C = 2

Output: [7, 6]

Step-by-Step Explanation:

Let's generate all possible combinations $A[i] + B[j]$ :
- 3 + 1 = 4
- 3 + 4 = 7
- 2 + 1 = 3
- 2 + 4 = 6
The complete list of sums is [4, 7, 3, 6].
Sorting them in descending order gives [7, 6, 4, 3].
We only need the top $C = 2$ sums, which are 7 and 6.

Example 2

Input: A = [1, 4, 2, 3], B = [2, 5, 1, 6], C = 4

Output: [10, 9, 9, 8]

Step-by-Step Explanation:

If we take the highest from $A$ (which is 4) and highest from $B$ (which is 6), the sum is 10.
The next highest could be 4 (from $A$ ) + 5 (from $B$ ) = 9.
Another high combination is 3 (from $A$ ) + 6 (from $B$ ) = 9.
The next highest is 4 (from $A$ ) + 4 (Wait, 4 is not in $B$ . The next valid combinations are 3+5=8 or 2+6=8).
The top 4 sums are 10, 9, 9, and 8.

3. Key Observations

Before jumping into solutions, here are the hidden truths of the problem:

Sorting Creates Predictability: In an unsorted array, the maximum sum could be anywhere. If you sort both arrays in descending order, the absolute highest sum is guaranteed to be $A[0] + B[0]$ .
The "Next Best" Candidates: Once you use $A[0] + B[0]$ , what is the next largest sum? It must be either $A[1] + B[0]$ or $A[0] + B[1]$ . There is no mathematical possibility for $A[2] + B[2]$ to be greater than those two.
Overlapping Paths: If you move from indices (0,0) to (1,0), and then to (1,1), you reach the same combination as moving from (0,0) to (0,1) and then to (1,1). We must avoid calculating and storing the same index pairs multiple times.

4. Intuition

Let's build the intuition using a visual matrix. Imagine we sort $A = [4, 3, 2, 1]$ and $B = [6, 5, 2, 1]$ in descending order. Now, imagine a 2D grid where the cell at row $i$ and column $j$ represents the sum $A[i] + B[j]$ .

Notice how the values naturally decrease as you move right or down.

The absolute maximum is at the top-left corner (0,0).
If we take (0,0), the "frontier" of the next possible largest sums are its immediate right neighbor (0,1) and immediate bottom neighbor (1,0).
To constantly keep track of the largest available sum on this expanding frontier, we need a data structure that acts like a VIP line, always pushing the largest value to the front. This is the exact definition of a Max-Heap (Priority Queue)!

5. Brute Force Solution

Thought Process

If we don't know the priority queue approach, the simplest way is to physically generate every single possible pair, store their sums in a massive list, sort that list, and return the first $C$ elements.

Algorithm

Create an empty list all_sums.
Loop $i$ from 0 to $N-1$ for array $A$ .
Inside, loop $j$ from 0 to $N-1$ for array $B$ .
Calculate $A[i] + B[j]$ and append it to all_sums.
Sort all_sums in descending order.
Return the first $C$ elements.

C++ Implementation

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> maxCombinationsBrute(vector<int>& A, vector<int>& B, int C) {
    vector<int> all_sums;
    int n = A.size();
    
    // Generate all N^2 combinations
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            all_sums.push_back(A[i] + B[j]);
        }
    }
    
    // Sort in descending order
    sort(all_sums.begin(), all_sums.end(), greater<int>());
    
    // Extract top C
    vector<int> result;
    for (int i = 0; i < C; i++) {
        result.push_back(all_sums[i]);
    }
    
    return result;
}

Optimal Solution (Max-Heap + Visited Set)

We will use a Max-Heap to track the largest sums on our "frontier" and a Hash Set to ensure we don't evaluate the same (i, j) coordinate twice.

Search Space

Instead of searching $N^2$ elements, we only search up to $C$ elements. By popping the heap $C$ times, we guarantee we've found the top $C$ sums.

The Logic

Sort both arrays in descending order. Now, $A[0]$ and $B[0]$ are the maximum elements.
Initialize a Max-Heap. Each element in the heap will store the sum and its original indices: (sum, (i, j)).
Initialize a Set to keep track of visited index pairs (i, j).
Push the first, guaranteed largest pair (A[0] + B[0], (0, 0)) into the heap and mark (0, 0) as visited.
Loop $C$ times:
- Pop the top element from the heap. This is your current maximum sum. Add it to your result array.
- From the indices (i, j) of the popped element, calculate its two neighbors in the conceptual matrix: (i + 1, j) and (i, j + 1).
- For each neighbor, if it hasn't been visited and is within bounds, push it into the heap and mark it as visited.

8. Core Logic: The Expanding Frontier

Let's look at why the queue only needs (i+1, j) and (i, j+1).

When you extract the maximum element (0,0), the next logical maximums can only be exactly one step down or one step right in our grid visualization.

If we didn't use a visited set, the path (0,0) -> (1,0) -> (1,1) and the path (0,0) -> (0,1) -> (1,1) would result in the coordinates (1,1) being pushed into the Max-Heap twice. This would ruin our top $C$ count with duplicate instances of the same combination. The set acts as our gatekeeper.

9. Dry Run

Let's dry run the Max-Heap approach.

$A = [1, 4, 2, 3]$ , $B = [2, 5, 1, 6]$ , $C = 4$ .
Sort descending: $A = [4, 3, 2, 1]$ , $B = [6, 5, 2, 1]$ .

Initialization:

Max-Heap: [ (10, (0,0)) ] (Sum is 4+6=10)
Visited Set: {(0,0)}
Result: []

Iteration 1:

Pop (10, (0,0)). Result becomes [10].
Check neighbor (1,0): $A[1]+B[0] = 3+6 = 9$ . Not visited. Push (9, (1,0)). Add to Set.
Check neighbor (0,1): $A[0]+B[1] = 4+5 = 9$ . Not visited. Push (9, (0,1)). Add to Set.
Max-Heap now: [ (9, (1,0)), (9, (0,1)) ]

Iteration 2:

Heap top is (9, (1,0)) (or (0,1), tie doesn't matter). Let's pop (9, (1,0)). Result = [10, 9].
Check neighbor (2,0): $A[2]+B[0] = 2+6 = 8$ . Push (8, (2,0)). Add to Set.
Check neighbor (1,1): $A[1]+B[1] = 3+5 = 8$ . Push (8, (1,1)). Add to Set.
Max-Heap now: [ (9, (0,1)), (8, (2,0)), (8, (1,1)) ]

Iteration 3:

Pop (9, (0,1)). Result = [10, 9, 9].
Check neighbor (1,1): Already in Visited Set! Skip. (This proves why the set is crucial).
Check neighbor (0,2): $A[0]+B[2] = 4+2 = 6$ . Push (6, (0,2)). Add to Set.
Max-Heap now: [ (8, (2,0)), (8, (1,1)), (6, (0,2)) ]

Iteration 4 (Final since $C=4$ ):

Top is (8, (2,0)) or (8, (1,1)). Pop one, say (8, (1,1)). Result = [10, 9, 9, 8].
Loop terminates.

Final Answer: [10, 9, 9, 8]. Exactly correct, without ever calculating the $1s$ and $2s$ .

10. Algorithm

Sort arrays $A$ and $B$ in descending order.
Create a Max-Heap that stores pairs in the format: pair<sum, pair<i, j>>.
Create a set<pair<int, int>> to track visited indices (i, j).
Push (A[0] + B[0], (0, 0)) into the heap and insert (0, 0) into the set.
Create an output array result.
Loop exactly $C$ times:
- Pop the top element from the heap. Append its sum to result.
- Extract its indices i and j.
- If i + 1 < N and (i + 1, j) is not in the set:
  - Push (A[i+1] + B[j], (i+1, j)) into the heap.
  - Insert (i+1, j) into the set.
- If j + 1 < N and (i, j + 1) is not in the set:
  - Push (A[i] + B[j+1], (i, j+1)) into the heap.
  - Insert (i, j+1) into the set.
Return result.

11. C++ Code

Here is the clean, interview-ready implementation using standard C++ STL data structures:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>

using namespace std;

vector<int> solve(vector<int> &A, vector<int> &B, int C) {
    int n = A.size();
    
    // Step 1: Sort both arrays in descending order
    sort(A.begin(), A.end(), greater<int>());
    sort(B.begin(), B.end(), greater<int>());
    
    // Max-Heap to store pairs of: (sum, (index_in_A, index_in_B))
    priority_queue<pair<int, pair<int, int>>> maxHeap;
    
    // Set to keep track of visited index pairs
    set<pair<int, int>> visited;
    
    vector<int> result;
    
    // Step 2: Initialize with the maximum possible combination
    maxHeap.push({A[0] + B[0], {0, 0}});
    visited.insert({0, 0});
    
    // Step 3: Pop C times to get the top C combinations
    for (int count = 0; count < C; count++) {
        // Extract the current maximum
        auto topElement = maxHeap.top();
        maxHeap.pop();
        
        int currentSum = topElement.first;
        int i = topElement.second.first;
        int j = topElement.second.second;
        
        result.push_back(currentSum);
        
        // Explore the neighbor one step down (i+1, j)
        if (i + 1 < n && visited.find({i + 1, j}) == visited.end()) {
            maxHeap.push({A[i + 1] + B[j], {i + 1, j}});
            visited.insert({i + 1, j});
        }
        
        // Explore the neighbor one step right (i, j+1)
        if (j + 1 < n && visited.find({i, j + 1}) == visited.end()) {
            maxHeap.push({A[i] + B[j + 1], {i, j + 1}});
            visited.insert({i, j + 1});
        }
    }
    
    return result;
}

12. Complexity Analysis

Time Complexity: * Sorting the two arrays takes $O(N \log N)$ .
- We run a loop $C$ times. Inside the loop, we push at most 2 elements into the Priority Queue. Insertion and extraction in a heap of size $C$ takes $O(\log C)$ . Looking up a pair in the std::set takes $O(\log C)$ .
- Therefore, the heap/set operations take $O(C \log C)$ .
- Total Time Complexity: $O(N \log N + C \log C)$ . This easily passes the $10^5$ constraints.
Space Complexity:
- The priority queue and the set will store at most $O(C)$ elements at any given time.
- Total Auxiliary Space Complexity: $O(C)$ .

13. Correctness Proof

Why are we absolutely sure no larger sum is skipped?

Heap Property: We process items strictly in the order of their sum. The max-heap guarantees we always look at the absolute largest known candidate next.
Monotonic Decay: Because the arrays are sorted descending, moving an index from $i$ to $i+1$ or $j$ to $j+1$ will strictly decrease or maintain the sum, never increase it.
Frontier Connectivity: Any arbitrary valid coordinate (x, y) in our grid can be reached by a series of right and down moves starting from (0, 0). Because we push the immediate right and down neighbors of every maximum element we pop, the largest unknown elements are mathematically guaranteed to already be sitting inside the heap waiting to be evaluated.

Common Mistakes

Watch out for these frequent pitfalls during interviews:

Forgetting the Visited Set: This is the #1 mistake. Without a set, paths crossing at (i+1, j+1) will insert duplicate pairs into the heap, causing your answer to contain repeated values that shouldn't exist.
Using Ascending Sort by Accident: If you sort ascending and start from (0,0), you are actually finding the Minimum Sum Combinations. If you sort ascending, you MUST start from (N-1, N-1) and explore (i-1, j) and (i, j-1). It's much easier to just sort descending.
Looping N times instead of C times: The problem explicitly asks for the top $C$ combinations. Ensure your extraction loop runs strictly bounded by $C$ .

15. Pattern Recognition

How do you know an unseen problem uses this exact logic? Look for the "Matrix BFS / Dijkstra on Grid" pattern mixed with a Heap.

Indicators:

The problem asks for the "Top $K$ " or " $K$ -th largest/smallest" of pairs or combinations from two sorted structures.
Generating all combinations is technically possible but leads to $O(N^2)$ Memory/Time Limit Exceeded.
The combinations can be visualized as a 2D grid where values strictly increase or decrease along rows and columns.

Video Reference:

reference

problem link:

https://www.naukri.com/code360/problems/k-max-sum-combinations_975322