1000. Dominating Pair Sums
A food critic scored n dishes: dish j has a flavour score a[j] and a texture score b[j]. Each query [x, y] asks for a dish whose flavour is at least x and whose texture is at least y, maximising the total a[j] + b[j].
Return an array with one entry per query: the best total, or -1 if no dish satisfies both thresholds. Arrays a and b have the same length, and a dish may be reused by many queries.
Target time O((n + q) log n) and space O(n + q); checking every dish for every query is too slow.
Example 1
- Input:
- a = [8,3,6,9,2]b = [4,7,5,1,9]queries = [[5,4],[3,6],[10,1],[0,9]]
- Output:
- [12,10,-1,11]
- Explanation:
For (5,4) dishes 0 and 2 qualify with totals 12 and 11, so 12; for (3,6) only dish 1 qualifies (total 10); no dish has flavour 10, so (10,1) gives -1; for (0,9) only dish 4 qualifies (total 11).
Example 2
- Input:
- a = [14,20,7]b = [2,2,16]queries = [[7,2],[15,2],[21,1]]
- Output:
- [23,22,-1]
- Explanation:
Query (7,2) accepts all three items with totals 16, 22 and 23, so 23; (15,2) accepts only the second item, total 22; (21,1) accepts none.
Constraints
1 ≤ n = a.length = b.length ≤ 105
0 ≤ q = queries.length ≤ 2000
0 ≤ a[j], b[j], x, y ≤ 105
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 1,600 msC++ 400 msJava 800 msJavaScript 800 msTypeScript 800 ms
Expected complexity
- Time
- O((n + q) log n)
- Space
- O(n + q)