Leetcode 2736: Maximum Sum Queries

You are given two 0-indexed integer arrays nums1 and nums2, each of length n, and a 1-indexed 2D array queries where queries[i] = [xi, yi].

For the ith query, find the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n), where nums1[j] >= xi and nums2[j] >= yi, or -1 if there is no j satisfying the constraints.

Return an array answer where answer[i] is the answer to the ith query.

Example 1:

Input: nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]
Output: [6,10,7]
Explanation: 
For the 1st query xi = 4 and yi = 1, we can select index j = 0 since nums1[j] >= 4 and nums2[j] >= 1. The sum nums1[j] + nums2[j] is 6, and we can show that 6 is the maximum we can obtain.

For the 2nd query xi = 1 and yi = 3, we can select index j = 2 since nums1[j] >= 1 and nums2[j] >= 3. The sum nums1[j] + nums2[j] is 10, and we can show that 10 is the maximum we can obtain. 
For the 3rd query xi = 2 and yi = 5, we can select index j = 3 since nums1[j] >= 2 and nums2[j] >= 5. The sum nums1[j] + nums2[j] is 7, and we can show that 7 is the maximum we can obtain.
Therefore, we return [6,10,7].

Example 2:

Input: nums1 = [3,2,5], nums2 = [2,3,4], queries = [[4,4],[3,2],[1,1]]
Output: [9,9,9]
Explanation: For this example, we can use index j = 2 for all the queries since it satisfies the constraints for each query.

Example 3:

Input: nums1 = [2,1], nums2 = [2,3], queries = [[3,3]]
Output: [-1]
Explanation: There is one query in this example with xi = 3 and yi = 3. For every index, j, either nums1[j] < xi or nums2[j] < yi. Hence, there is no solution.

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
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 10^9

Problem Analysis:

This problem is asked to query maximum sum of nums1[i] + nums2[i], 0 ≤ i <nums1.size(), which restrict nums1[i] ≥ queries[j][0] and nums2[i] ≥ queries[j][1], 0 ≤ j <queries.size()

We can follow these steps to solve the problem:

1. we sort nums1
2. sort queries with first item in descent order
3. because nums1 and queries are sorted, we insert the pairs of (nums2[j], sum) into a map that data in map satisfies the restrict of nums1 part
4. when insert pair of (nums2[j], sum) into a map, we search minimum position that ≥ nums2[j], we name the position as k, we delete the data in map that key < k and the map[key] ≤ sum
5. query the map value that the minimum key ≥ queries[i][1] is the answer (as the delete operations in step 4 is a little tricky)

iterate the sorted queries with step 3–5, we can get the final answers

Solution

class Solution {
public:
  vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
    vector<pair<int, int>> data(nums1.size());
    for (int i = 0; i < data.size(); ++i) data[i] = make_pair(nums1[i], nums2[i]);
    sort(data.begin(), data.end());
    vector<int> indices(queries.size());
    iota(indices.begin(), indices.end(), 0);
    sort(indices.begin(), indices.end(), [&](int left, int right) {
      return queries[left][0] > queries[right][0];
    });
    vector<int> res(queries.size());
    map<int, int> values;
    for (int i = 0, j = nums1.size() - 1; i < queries.size(); ++i) {
      for (; j >= 0 && data[j].first >= queries[indices[i]][0]; 
           update(values, data[j].second, data[j].first + data[j].second), --j) 
        ;
      res[indices[i]] = query(values, queries[indices[i]][1]);
    }

    return res;
  }

private:
  void update(map<int, int>& values, int key, int value) {
    auto it = values.lower_bound(key);
    if (it != values.end() && it->second >= value) return;
    if (it != values.begin()) {
      --it;
      while (it->second <= value) {
        if (it == values.begin()) {
          values.erase(it);
          break;
        } else {
          values.erase(it--);
        }
      }
    }
    values.insert({key, value});
  }

  int query(const map<int, int>& values, int key) {
    const auto it = values.lower_bound(key);
    return it == values.end() ? -1 : it->second;
  }
};

Time complexity is O(num1 log(num1), queries log(queries))

Space complexity is O(num1, queries)