Lightest K Pairs
MediumHeap / Priority Queue
Problem
A shop sells bundles made of one item from list a and one from list b; both lists of prices are sorted in non-decreasing order. Bundle (i, j) costs a[i] + b[j].
Return the k cheapest bundles as [a[i], b[j]] pairs, cheapest first. Bundles with the same cost are ordered by smaller i first, then by smaller j.
Example 1
- Input:
- a = [1, 4, 10], b = [2, 3, 8], k = 4
- Output:
- [[1, 2], [1, 3], [4, 2], [4, 3]]
Costs: (0,0)=3, (0,1)=4, (1,0)=6, (1,1)=7, (0,2)=9, ...
Example 2
- Input:
- a = [1, 1], b = [1, 2], k = 3
- Output:
- [[1, 1], [1, 1], [1, 2]]
(0,0) and (1,0) both cost 2; (0,0) comes first because i = 0 < 1. Then (0,1) costs 3.
Constraints
- 1 ≤ a.length, b.length ≤ 10^5
- -10^9 ≤ a[i], b[j] ≤ 10^9
- a and b are sorted in non-decreasing order
- 1 ≤ k ≤ min(10^4, a.length · b.length)
Hint
Show the first hint
Picture the m × n grid of costs a[i] + b[j]. Because both lists are sorted, each row is sorted left to right.
Walkthrough
How to approach it
01Clarify before coding
- Are both lists sorted? Yes, non-decreasing. That is what makes a frontier search possible.
- How are equal costs ordered? By i, then j, so the answer is unique.
- Can k exceed the number of bundles? No, k ≤ m·n.
02Brute force
Generate all m·n bundles, sort by (cost, i, j) and take the first k.
Cost: O(mn log(mn)) time and O(mn) space: up to 10^10 bundles, impossible.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.