Maximum Sum Queries

Hard
1398.

Maximum Sum Queries

Maximum Sum Queries is a hard coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

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.length
  • n == nums1.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^9
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= x_i, y_i <= 10^9
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @param {number[][]} queries
 * @return {number[]}
 */
var maximumSumQueries = function(nums1, nums2, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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.length
  • n == nums1.length
  • 1 <= n <= 10^5
  • 1 <= nums1[i], nums2[i] <= 10^9
  • 1 <= queries.length <= 10^5
  • queries[i].length == 2
  • 1 <= x_i, y_i <= 10^9

Hints for Maximum Sum Queries

  1. Hint 1

    Answer the queries offline in decreasing order of x, so the set of indices passing the first test only ever grows.

  2. Hint 2

    Among the indices added so far, one with a smaller nums2 and a smaller sum than another is useless. What remains can be kept so that nums2 increases while the sum decreases.

  3. 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

  1. Sort indices by nums1 descending and query indices by x descending.
  2. For each query, first add every point with nums1 >= x. A new point (b, s) is skipped if the stack top already has nums2 >= b (that point has at least as large nums1 and nums2, so it dominates). Otherwise pop entries whose sum is <= s, then push (b, s).
  3. The stack has nums2 strictly increasing and sums strictly decreasing from bottom to top. Binary-search the first entry with nums2 >= y; its sum is the answer, or -1 if 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 >= on x.
  • 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 res

Java

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