Cheapest K Pairings Across Two Sorted Menus
Implement cheapestPairings
Two menus list dish prices in non-decreasing order. A pairing takes one dish from each menu and costs the sum of the two prices. Return the k cheapest pairings, cheapest first; if two pairings cost the same, the one with the cheaper menuA dish comes first.
Building and sorting all n × m pairings works, but the sorted menus make it unnecessary: the cheapest pairing not yet chosen can only be the next untaken pairing in some row. A min-heap that holds one candidate per row finds each next pairing in O(log n) and never builds the ones that can't matter.
Example 1:
Input: menuA = [1,4,9], menuB = [2,3,8], k = 4
Output: [[1,2],[1,3],[4,2],[4,3]]
Example 2:
Input: menuA = [2,3], menuB = [7], k = 2
Output: [[2,7],[3,7]]
Example 3:
Input: menuA = [5], menuB = [7], k = 1
Output: [[5,7]]
+ 10 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ menuA.length, menuB.length ≤ 20 - ●
-100 ≤ menuA[i], menuB[i] ≤ 100, and both menus are sorted in non-decreasing order (duplicates allowed) - ●
1 ≤ k ≤ menuA.length × menuB.length - ●
A pairing is [a, b] with a taken from menuA and b from menuB; return the k pairings with the smallest a + b, cheapest first, breaking equal totals by the smaller a first
menuA =
menuB =
k =