Maximum Sum Queries

• 1. Initialize an answer array of size q (number of queries) with -1.
• 2. For each query i from 0 to q-1 with [x, y]:
• 3. Initialize max_sum = -1.
• 4. For each index j from 0 to n-1:
• 5. If `nums1[j] >= x` and `nums2[j] >= y`:
• 6. Update `max_sum = max(max_sum, nums1[j] + nums2[j])`.
• 7. Set answer[i] = max_sum.
• 8. Return answer.

We initialize an answer array for all queries with a default value of -1. We then loop through each query (xi, yi). Inside this loop, we start another loop that iterates through all indices j from 0 to n-1. For each index j, we perform a check: if (nums1[j] >= xi && nums2[j] >= yi). If the condition is true, we calculate the sum s = nums1[j] + nums2[j] and update the maximum sum for the current query: answer[i] = max(answer[i], s). After checking all j for a given query i, answer[i] will hold the required maximum sum, or -1 if no valid pair was found. This process is repeated for all queries.

1class Solution {2    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {3        int n = nums1.length;4        int q = queries.length;5        int[] answer = new int[q];6 7        for (int i = 0; i < q; i++) {8            int x = queries[i][0];9            int y = queries[i][1];10            int maxSum = -1;11            for (int j = 0; j < n; j++) {12                if (nums1[j] >= x && nums2[j] >= y) {13                    maxSum = Math.max(maxSum, nums1[j] + nums2[j]);14                }15            }16            answer[i] = maxSum;17        }18        return answer;19    }20}

• 1. Create (num1, num2) pairs from nums1 and nums2. Sort these pairs by num1 in descending order.
• 2. Create (x, y, original_index) query objects. Sort these by x in descending order.
• 3. Perform coordinate compression on nums2 values:
  • a. Collect all unique nums2 values.
  • b. Sort them to create a mapping from each unique y-value to a rank (0, 1, ...).
• 4. Initialize a Segment Tree of a size corresponding to the number of unique y-values. Initialize all its values to -1.
• 5. Initialize an answer array and a pointer pair_idx = 0.
• 6. Iterate through the sorted queries:
  • a. For the current query (x, y, original_index), advance pair_idx to process all pairs (num1, num2) where num1 >= x.
  • b. For each such pair, get the rank of num2 and update the Segment Tree at that rank with the sum num1 + num2.
  • c. Find the rank for the query's y value (or the smallest value greater than it).
  • d. Query the Segment Tree for the maximum value in the range from y's rank to the end.
  • e. Store the result in answer[original_index].
• 7. Return answer.

The problem asks for max(nums1[j] + nums2[j]) for pairs where nums1[j] >= x and nums2[j] >= y. We can rephrase this: for a fixed x, we consider all pairs (nums1[j], nums2[j]) with nums1[j] >= x. Among these, we need to find one with nums2[j] >= y that maximizes the sum. If we sort both the number pairs (by nums1) and queries (by x) in descending order, we can process them together. As we move to queries with smaller x values, the set of eligible number pairs only grows.

The algorithm is as follows:

1. Combine nums1 and nums2 into a list of pairs (num1, num2) and sort it in descending order based on num1.
2. Augment the queries array to store the original index of each query, i.e., (x, y, original_index), and sort it in descending order based on x.
3. Since the values in nums2 can be very large, we use coordinate compression on all nums2 values to map them to a smaller range of indices [0, k-1], where k is the number of unique nums2 values.
4. We build a Segment Tree over these compressed y-coordinates. Each node in the tree will store the maximum sum found so far for the corresponding range of y-coordinates.
5. We iterate through the sorted queries. For each query (x, y), we first add all number pairs (num1, num2) with num1 >= x to our data structure. Since both are sorted, we can use a pointer to keep track of which pairs have been processed.
6. For each such pair (num1, num2), we find the compressed coordinate for num2 and update the Segment Tree at that coordinate with the sum num1 + num2. The update operation ensures we store the maximum sum for that coordinate.
7. After updating the Segment Tree with all relevant pairs, we query it to find the maximum sum for all y-coordinates greater than or equal to the query's y. This corresponds to a range maximum query on the Segment Tree.
8. The result of this query is the answer for the current query, which we store in an answer array at its original index.

This approach avoids re-computation by cleverly ordering operations and using a data structure that supports fast updates and range queries. A balanced binary search tree (like Java's TreeMap) could also be used instead of a Segment Tree to maintain a monotonic chain of (y, sum) candidates, achieving a similar time complexity.

1class Solution {2    // Segment Tree Node/Array implementation3    int[] tree;4    int size;5 6    void update(int node, int start, int end, int idx, int val) {7        if (start == end) {8            tree[node] = Math.max(tree[node], val);9            return;10        }11        int mid = start + (end - start) / 2;12        if (start <= idx && idx <= mid) {13            update(2 * node, start, mid, idx, val);14        } else {15            update(2 * node + 1, mid + 1, end, idx, val);16        }17        tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);18    }19 20    int query(int node, int start, int end, int l, int r) {21        if (r < start || end < l || l > r) {22            return -1;23        }24        if (l <= start && end <= r) {25            return tree[node];26        }27        int mid = start + (end - start) / 2;28        int p1 = query(2 * node, start, mid, l, r);29        int p2 = query(2 * node + 1, mid + 1, end, l, r);30        return Math.max(p1, p2);31    }32 33    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {34        int n = nums1.length;35        int[][] pairs = new int[n][2];36        for (int i = 0; i < n; i++) {37            pairs[i][0] = nums1[i];38            pairs[i][1] = nums2[i];39        }40        // Sort pairs by nums1 descending41        Arrays.sort(pairs, (a, b) -> Integer.compare(b[0], a[0]));42 43        int q = queries.length;44        int[][] indexedQueries = new int[q][3];45        for (int i = 0; i < q; i++) {46            indexedQueries[i][0] = queries[i][0];47            indexedQueries[i][1] = queries[i][1];48            indexedQueries[i][2] = i;49        }50        // Sort queries by x descending51        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b[0], a[0]));52 53        // Coordinate Compression for y values54        TreeSet<Integer> ySet = new TreeSet<>();55        for (int num : nums2) {56            ySet.add(num);57        }58        Map<Integer, Integer> yMap = new HashMap<>();59        int rank = 0;60        for (int y : ySet) {61            yMap.put(y, rank++);62        }63        64        // Segment Tree initialization65        this.size = yMap.size();66        this.tree = new int[4 * size];67        Arrays.fill(tree, -1);68 69        int[] ans = new int[q];70        int pairIndex = 0;71 72        for (int i = 0; i < q; i++) {73            int x = indexedQueries[i][0];74            int y = indexedQueries[i][1];75            int originalIndex = indexedQueries[i][2];76 77            while (pairIndex < n && pairs[pairIndex][0] >= x) {78                int num1 = pairs[pairIndex][0];79                int num2 = pairs[pairIndex][1];80                int sum = num1 + num2;81                int yRank = yMap.get(num2);82                update(1, 0, size - 1, yRank, sum);83                pairIndex++;84            }85 86            Integer yFloor = ySet.ceiling(y);87            if (yFloor == null) {88                ans[originalIndex] = -1;89            } else {90                int yRankQuery = yMap.get(yFloor);91                ans[originalIndex] = query(1, 0, size - 1, yRankQuery, size - 1);92            }93        }94        return ans;95    }96}