DiffPush Tier Heaps · Hard Problems O(n log n + k log n) · O(n)
A calibration rig pairs readings from two sensor banks, one value from each, producing a correlation score per pair. The lab only cares about the k strongest pairings, listed strongest-first. Rather than scoring all n*n pairs, the rig seeds a shortlist with each bank-A reading paired to bank-B's strongest value, then repeatedly demotes a pair to its next-weaker bank-B partner.
Input: Two integer arrays A and B of equal size N, and an integer K.
Output: Return the K largest pair sums, sorted in non-increasing order.
1 <= N <= 10^51 <= K <= N-10^9 <= A[i], B[i] <= 10^9Input: {"A":[3,2],"B":[1,4],"K":2}
Output: [7,6]
3+4=7 leads; the runner-up is 2+4=6.
Input: {"A":[1,4,2,3],"B":[2,5,1,6],"K":4}
Output: [10,9,9,8]
The strongest pairings all anchor on B's largest values.