995. Dominating Pair Sums
A food-truck festival has n stalls. Stall j has a footfall score a[j] and a rating b[j]; its overall value is a[j] + b[j]. Visitors submit requests, and request queries[i] = [x, y] means: they only consider stalls with footfall at least x and rating at least y.
For every request, report the highest overall value among the stalls that qualify, or -1 if no stall qualifies. Return an array result where result[i] answers queries[i]. Several stalls may share scores, and a stall may qualify for many requests.
Example 1
- Input:
- a = [4,3,1,2]b = [2,4,9,5]queries = [[4,1],[1,5],[3,7]]
- Output:
- [6,10,-1]
- Explanation:
Query [4,1] only admits item 0 (sum 6); query [1,5] admits item 2 (sum 10) and item 3 (sum 7), best 10; query [3,7] has no item with b >= 7 and a >= 3, so -1.
Example 2
- Input:
- a = [5,5], b = [5,1], queries = [[5,5],[6,0],[0,0]]
- Output:
- [10,-1,10]
- Explanation:
Only item 0 satisfies [5,5] (sum 10); no item has a >= 6; with thresholds [0,0] both qualify and the larger sum is 10.
Example 3
- Input:
- a = [1,8,3], b = [7,2,6], queries = [[2,2]]
- Output:
- [10]
- Explanation:
Items 1 and 2 both have a >= 2 and b >= 2; their sums are 10 and 9, so the answer is 10.
Constraints
- 1 ≤ n = a.length = b.length ≤ 105
- 1 ≤ queries.length ≤ 105
- 0 ≤ a[j], b[j], x, y ≤ 109
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 400 msC++ 100 msJava 200 msJavaScript 200 msTypeScript 200 ms
Expected complexity
- Time
- O((n + q) log (n + q))
- Space
- O(n + q)