2736. Maximum Sum Queries

Problem

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 <= 105
• 1 <= nums1[i], nums2[i] <= 109&nbsp;
• 1 <= queries.length <= 105
• queries[i].length == 2
• xi == queries[i][1]
• yi == queries[i][2]
• 1 <= xi, yi <= 109

Solution (Java)

class Solution {
    public int[] maximumSumQueries(int[] a1, int[] a2, int[][] queries) {
        int n = a1.length;
        int a[][] = new int[n][2];
        for(int i = 0; i < n; i++){
            a[i][0] = a1[i];
            a[i][1] = a2[i];
        }
        Arrays.sort(a2);
        hm = new TreeMap<>();
        int k = 0;
        for(int i = 0; i < n; i++)
            if(!hm.containsKey(a2[i]))
                hm.put(a2[i], k++);

        Arrays.sort(a,
            new Comparator<int[]>(){
                public int compare(int x[], int y[]){
                    return x[0] - y[0];
                }
            }
        );

        for(int i = 0; i < queries.length; i++){
            queries[i] = new int[]{queries[i][0], queries[i][1], i};
        }
        Arrays.sort(queries,
            new Comparator<int[]>(){
                public int compare(int x[], int y[]){
                    return -x[0] + y[0];
                }
            }
        );
        int max = 0;
        int ans[] = new int[queries.length];
        int j = 0;
        int i = a.length - 1;

        seg = new int[4 * hm.size() + 4];
        Arrays.fill(seg, -1);
        while(j < queries.length){
            while(i > -1 && a[i][0] >= queries[j][0]){
                update(0, hm.size() - 1, hm.get(a[i][1]), a[i][0] + a[i][1], 0);
                i--;
            }

            if(hm.ceilingKey(queries[j][1]) == null){
                ans[queries[j][2]] = -1;
            } else{
                ans[queries[j][2]] = find(0, hm.size() - 1, hm.ceilingEntry(queries[j][1]).getValue(), hm.size() - 1, 0);
            }
            j++;
        }
        while(j < queries.length)
            ans[queries[j++][2]] = -1;
        return ans;
    }
    private void update(int low, int high, int ind, int val, int node){
        if(low == high){
            seg[node] = Math.max(seg[node], val);
            return;
        }
        int mid = (low + high) >> 1;
        if(ind <= mid)
            update(low, mid, ind, val, 2 * node + 1);
        else
            update(mid + 1, high, ind, val, 2 * node + 2);
        seg[node] = Math.max(seg[2 * node + 1], seg[2 * node + 2]);
    }
    private int find(int low, int high, int l, int r, int node){
        if(low > r || high < l)
            return -1;
        if(low >= l && high <= r)
            return seg[node];
        int mid = (low + high) >> 1;
        return Math.max(find(low, mid, l, r, 2 * node + 1), find(mid + 1, high, l, r, 2 * node + 2));
    }
    private int seg[];
    private TreeMap<Integer, Integer> hm;
}

Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).