Maximum Sum Queries — Solution in Python, Java & C++
Maximum Sum Queries solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem on arrays and sorting.
Maximum Sum Queries is a hard coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.
- Difficulty: Hard
- Topics: Arrays, Sorting, Binary Search, Monotonic Stack
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given two arrays nums1 and nums2 of the same length n and a list of queries queries[i] = [x_i, y_i].
For each query, look at every index j with nums1[j] >= x_i and nums2[j] >= y_i, and take the largest nums1[j] + nums2[j] among them. If no index qualifies, the answer is -1.
Return the answers in query order.
Example 1
Input: nums1 = [5,2,7,3], nums2 = [1,8,2,6], queries = [[3,2],[1,7],[6,3],[2,1]]
Output: [9,10,-1,10]
Explanation: For [3,2] the indices holding (7,2) and (3,6) qualify, both summing to 9; for [6,3] only (7,2) passes the first test and it fails the second.
Example 2
Input: nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
Output: [9,9,9]
Constraints
nums1.length == nums2.lengthn == nums1.length1 <= n <= 10^51 <= nums1[i], nums2[i] <= 10^91 <= queries.length <= 10^5queries[i].length == 21 <= x_i, y_i <= 10^9
Hints for Maximum Sum Queries
Hint 1
Answer the queries offline in decreasing order of
x, so the set of indices passing the first test only ever grows.Hint 2
Among the indices added so far, one with a smaller
nums2and a smaller sum than another is useless. What remains can be kept so thatnums2increases while the sum decreases.Hint 3
For a query, binary-search that list for the first entry with
nums2 >= y— its sum is the best available.
How to solve Maximum Sum Queries
Process points by decreasing nums1 and queries by decreasing x. Keep only the Pareto-useful points in a stack ordered by increasing nums2 and decreasing sum; a query then needs one binary search on nums2.
Approach
- Sort indices by
nums1descending and query indices byxdescending. - For each query, first add every point with
nums1 >= x. A new point(b, s)is skipped if the stack top already hasnums2 >= b(that point has at least as largenums1andnums2, so it dominates). Otherwise pop entries whose sum is<= s, then push(b, s). - The stack has
nums2strictly increasing and sums strictly decreasing from bottom to top. Binary-search the first entry withnums2 >= y; its sum is the answer, or-1if there is none.
Why it works
Every point already in the stack has nums1 at least the new point's, so if it also has nums2 at least as large it also has at least the same sum — the new point can never be the unique best. A popped entry has smaller nums2 and no larger sum than the new point, so any query it could serve is served at least as well by the new point. These rules preserve the two monotone orders, which make the first entry meeting the nums2 bound the one with the largest sum. Points stay valid for later queries because their x only decreases.
Complexity
- Time —
O((n + q) log(n + q)) - Space —
O(n + q)
Pitfalls
- Sums reach 2 · 10^9, which still fits a signed 32-bit integer — but only just; be careful with any extra arithmetic.
- Points must be added before answering a query, using
>=onx. - Return answers in the original query order, not the sorted order.
Reference solution
Python
from typing import List
def maximumSumQueries(nums1: List[int], nums2: List[int], queries: List[List[int]]) -> List[int]:
n = len(nums1)
order = sorted(range(n), key=lambda i: -nums1[i])
qorder = sorted(range(len(queries)), key=lambda i: -queries[i][0])
res = [-1] * len(queries)
st_b, st_s = [], []
j = 0
for qi in qorder:
x, y = queries[qi]
while j < n and nums1[order[j]] >= x:
b = nums2[order[j]]
s = nums1[order[j]] + b
if not st_b or st_b[-1] < b:
while st_s and st_s[-1] <= s:
st_s.pop()
st_b.pop()
st_b.append(b)
st_s.append(s)
j += 1
lo, hi = 0, len(st_b)
while lo < hi:
mid = (lo + hi) // 2
if st_b[mid] < y:
lo = mid + 1
else:
hi = mid
if lo < len(st_b):
res[qi] = st_s[lo]
return resJava
public static int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.length, qn = queries.length;
Integer[] order = new Integer[n];
for (int i = 0; i < n; i++) order[i] = i;
Arrays.sort(order, (p, q) -> Integer.compare(nums1[q], nums1[p]));
Integer[] qorder = new Integer[qn];
for (int i = 0; i < qn; i++) qorder[i] = i;
Arrays.sort(qorder, (p, q) -> Integer.compare(queries[q][0], queries[p][0]));
int[] res = new int[qn];
Arrays.fill(res, -1);
int[] stB = new int[n];
long[] stS = new long[n];
int top = 0, j = 0;
for (int qi : qorder) {
int x = queries[qi][0], y = queries[qi][1];
while (j < n && nums1[order[j]] >= x) {
int b = nums2[order[j]];
long s = (long) nums1[order[j]] + b;
if (top == 0 || stB[top - 1] < b) {
while (top > 0 && stS[top - 1] <= s) top--;
stB[top] = b;
stS[top] = s;
top++;
}
j++;
}
int lo = 0, hi = top;
while (lo < hi) {
int mid = (lo + hi) >>> 1;
if (stB[mid] < y) lo = mid + 1; else hi = mid;
}
if (lo < top) res[qi] = (int) stS[lo];
}
return res;
}C++
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums1.size(), qn = queries.size();
vector<int> order(n), qorder(qn);
for (int i = 0; i < n; i++) order[i] = i;
for (int i = 0; i < qn; i++) qorder[i] = i;
sort(order.begin(), order.end(), [&](int p, int q) { return nums1[p] > nums1[q]; });
sort(qorder.begin(), qorder.end(), [&](int p, int q) { return queries[p][0] > queries[q][0]; });
vector<int> res(qn, -1);
vector<int> stB;
vector<long long> stS;
int j = 0;
for (int qi : qorder) {
int x = queries[qi][0], y = queries[qi][1];
while (j < n && nums1[order[j]] >= x) {
int b = nums2[order[j]];
long long s = (long long)nums1[order[j]] + b;
if (stB.empty() || stB.back() < b) {
while (!stS.empty() && stS.back() <= s) { stS.pop_back(); stB.pop_back(); }
stB.push_back(b);
stS.push_back(s);
}
j++;
}
int lo = lower_bound(stB.begin(), stB.end(), y) - stB.begin();
if (lo < (int)stB.size()) res[qi] = (int)stS[lo];
}
return res;
}JavaScript
var maximumSumQueries = function(nums1, nums2, queries) {
var n = nums1.length;
var order = [];
for (var i = 0; i < n; i++) order.push(i);
order.sort(function(p, q) { return nums1[q] - nums1[p]; });
var qorder = [];
for (var t = 0; t < queries.length; t++) qorder.push(t);
qorder.sort(function(p, q) { return queries[q][0] - queries[p][0]; });
var res = new Array(queries.length).fill(-1);
var stB = [], stS = [];
var j = 0;
for (var u = 0; u < qorder.length; u++) {
var qi = qorder[u], x = queries[qi][0], y = queries[qi][1];
while (j < n && nums1[order[j]] >= x) {
var b = nums2[order[j]], s = nums1[order[j]] + b;
if (stB.length === 0 || stB[stB.length - 1] < b) {
while (stS.length > 0 && stS[stS.length - 1] <= s) { stS.pop(); stB.pop(); }
stB.push(b);
stS.push(s);
}
j++;
}
var lo = 0, hi = stB.length;
while (lo < hi) {
var mid = (lo + hi) >> 1;
if (stB[mid] < y) lo = mid + 1; else hi = mid;
}
if (lo < stB.length) res[qi] = stS[lo];
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms