558. Cheapest K Pairs
A catering service sells starters and desserts. The array a lists the prices of the starters and the array b the prices of the desserts, both sorted in non-decreasing order (a price may repeat). A menu is a pair made of one starter and one dessert, identified by their positions (i, j), and costs a[i] + b[j].
Return the k cheapest menus as an array of [a[i], b[j]] pairs. Order them by total cost; when two menus cost the same, the one with the smaller i comes first, and if i is also equal, the one with the smaller j. Equal prices at different positions give different menus that may both appear.
There are far too many pairs to build them all; aim for O(k log min(k, |a|)) time.
Example 1
- Input:
- a = [1,4,8], b = [2,3,9], k = 4
- Output:
- [[1,2],[1,3],[4,2],[4,3]]
- Explanation:
The sums in order are 3 (1+2), 4 (1+3), 6 (4+2), 7 (4+3), so those four pairs are returned.
Example 2
- Input:
- a = [2,2], b = [5,5], k = 3
- Output:
- [[2,5],[2,5],[2,5]]
- Explanation:
All four menus cost 7; index order picks (0,0), (0,1) and (1,0), which as values are [2,5], [2,5], [2,5].
Example 3
- Input:
- a = [-3,0], b = [-1,6], k = 2
- Output:
- [[-3,-1],[0,-1]]
- Explanation:
The cheapest sums are -4 (-3+-1) and -1 (0+-1), listed by cost.
Constraints
- 1 ≤
a.length,b.length≤ 105 - -109 ≤
a[i],b[j]≤ 109, both arrays sorted in non-decreasing order - 1 ≤
k≤ min(300,a.length*b.length) - Sums can reach 2 * 109: use 64-bit arithmetic
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 3,200 msC++ 800 msJava 1,600 msJavaScript 1,600 msTypeScript 1,600 ms
Expected complexity
- Time
- O(k log min(k, |a|))
- Space
- O(min(k, |a|))