Cheapest K Pairings Across Two Sorted Menus
Solve this ProblemTwo 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.
Test Case 1:
Test Case 2:
Test Case 3:
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
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Build Every Pairing, Then Sort
BruteGenerate every possible [a, b] pairing — all n × m of them — sort the whole list by total (then by a), and keep the first k. It is straightforward, but it materialises and orders the entire n × m grid of pairings even when k is tiny, so both the time and the memory scale with the product of the menu sizes.
O(n·m · log(n·m))O(n·m)1class Solution {
2 public int[][] cheapestPairings(int[] menuA, int[] menuB, int k) {
3 List<int[]> pairs = new ArrayList<>();
4 for (int a : menuA) {
5 for (int b : menuB) pairs.add(new int[]{a, b});
6 }
7 pairs.sort((x, y) -> {
8 if (x[0] + x[1] != y[0] + y[1]) return (x[0] + x[1]) - (y[0] + y[1]);
9 return x[0] - y[0];
10 });
11 int[][] result = new int[k][];
12 for (int i = 0; i < k; i++) result[i] = pairs.get(i);
13 return result;
14 }
15}Optimal — Min-Heap Frontier Over the Sorted Grid
OptimalBecause both menus are sorted, the pairing totals form a grid that only grows to the right and downward: pairing (i, j) can never be cheaper than (i, j−1). So the cheapest unused pairing is always on a "frontier". Seed a min-heap with the first pairing of each of the first k rows — (i, 0) — keyed by (total, i, j). Pop the cheapest, record it, then push its right neighbour (i, j+1) as the row's new frontier. After k pops the answer is complete, and the heap never held more than min(n, k) entries, so only the pairings that could actually be next are ever built.
O(k log min(n, k))O(min(n, k))1class Solution {
2 public int[][] cheapestPairings(int[] menuA, int[] menuB, int k) {
3 PriorityQueue<int[]> frontier = new PriorityQueue<>((x, y) -> {
4 if (x[0] != y[0]) return x[0] - y[0];
5 if (x[1] != y[1]) return x[1] - y[1];
6 return x[2] - y[2];
7 });
8 for (int i = 0; i < Math.min(k, menuA.length); i++) {
9 frontier.offer(new int[]{menuA[i] + menuB[0], i, 0});
10 }
11 int[][] result = new int[k][2];
12 for (int taken = 0; taken < k; taken++) {
13 int[] best = frontier.poll();
14 result[taken][0] = menuA[best[1]];
15 result[taken][1] = menuB[best[2]];
16 if (best[2] + 1 < menuB.length) {
17 frontier.offer(new int[]{menuA[best[1]] + menuB[best[2] + 1], best[1], best[2] + 1});
18 }
19 }
20 return result;
21 }
22}