# Maximum Sum Queries
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-sum-queries)
Canonical: https://scaleengineer.com/dsa/problems/maximum-sum-queries
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Stack, Monotonic Stack, Binary Indexed Tree, Segment Tree
---
## 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 `
* `1 <= queries.length <= 105`
* `queries[i].length == 2`
* `xi == queries[i][1]`
* `yi == queries[i][2]`
* `1 <= xi, yi <= 109`

# Approaches
## Brute Force Iteration
The most straightforward solution is to iterate through all the given numbers for each query. For every query `(x, y)`, we check every pair `(nums1[j], nums2[j])` to see if it satisfies the conditions `nums1[j] >= x` and `nums2[j] >= y`. We keep track of the maximum sum `nums1[j] + nums2[j]` found among all valid pairs.
**Time:** O(n * q), where `n` is the length of `nums1`/`nums2` and `q` is the number of queries. For each of the `q` queries, we iterate through `n` elements. · **Space:** O(q) to store the answer array. If the output array is not considered, the space complexity is O(1).
**Pros:** Very simple to understand and implement.; Requires no complex data structures.
**Cons:** Highly inefficient. The nested loops lead to a quadratic time complexity in the worst case.; Will result in a "Time Limit Exceeded" (TLE) error for large inputs as per the problem constraints.
### Explanation
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.
```java
class Solution {
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        int q = queries.length;
        int[] answer = new int[q];

        for (int i = 0; i < q; i++) {
            int x = queries[i][0];
            int y = queries[i][1];
            int maxSum = -1;
            for (int j = 0; j < n; j++) {
                if (nums1[j] >= x && nums2[j] >= y) {
                    maxSum = Math.max(maxSum, nums1[j] + nums2[j]);
                }
            }
            answer[i] = maxSum;
        }
        return answer;
    }
}
```
### Algorithm
- 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`.

## Offline Processing with Sorting and Segment Tree
A much more efficient approach involves processing the queries "offline". Instead of handling them one by one in the given order, we can reorder them to answer them more efficiently. The core idea is to sort both the number pairs and the queries by one dimension (e.g., `nums1` and `x` values). This allows us to process them in a single sweep. As we iterate through the sorted queries, we add the relevant number pairs to a data structure that can efficiently query on the second dimension (e.g., `nums2` and `y` values). A Segment Tree is a suitable data structure for this purpose.
**Time:** O(N log N + M log M), where N is `nums1.length` and M is `queries.length`. Sorting pairs takes O(N log N). Sorting queries takes O(M log M). The main loop involves `N` segment tree updates (O(N log N)) and `M` segment tree queries (O(M log N)). The total is dominated by these terms. · **Space:** O(N + M). We need O(N) for pairs and coordinate compression data, O(M) for indexed queries and the answer array, and O(N) for the segment tree.
**Pros:** Highly efficient, with a time complexity that is logarithmic with respect to the input sizes.; A standard and powerful technique for solving 2D query problems.
**Cons:** More complex to implement than the brute-force approach.; Requires understanding of advanced data structures like Segment Trees and concepts like coordinate compression.
### Explanation
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.
```java
class Solution {
    // Segment Tree Node/Array implementation
    int[] tree;
    int size;

    void update(int node, int start, int end, int idx, int val) {
        if (start == end) {
            tree[node] = Math.max(tree[node], val);
            return;
        }
        int mid = start + (end - start) / 2;
        if (start <= idx && idx <= mid) {
            update(2 * node, start, mid, idx, val);
        } else {
            update(2 * node + 1, mid + 1, end, idx, val);
        }
        tree[node] = Math.max(tree[2 * node], tree[2 * node + 1]);
    }

    int query(int node, int start, int end, int l, int r) {
        if (r < start || end < l || l > r) {
            return -1;
        }
        if (l <= start && end <= r) {
            return tree[node];
        }
        int mid = start + (end - start) / 2;
        int p1 = query(2 * node, start, mid, l, r);
        int p2 = query(2 * node + 1, mid + 1, end, l, r);
        return Math.max(p1, p2);
    }

    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        int[][] pairs = new int[n][2];
        for (int i = 0; i < n; i++) {
            pairs[i][0] = nums1[i];
            pairs[i][1] = nums2[i];
        }
        // Sort pairs by nums1 descending
        Arrays.sort(pairs, (a, b) -> Integer.compare(b[0], a[0]));

        int q = queries.length;
        int[][] indexedQueries = new int[q][3];
        for (int i = 0; i < q; i++) {
            indexedQueries[i][0] = queries[i][0];
            indexedQueries[i][1] = queries[i][1];
            indexedQueries[i][2] = i;
        }
        // Sort queries by x descending
        Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b[0], a[0]));

        // Coordinate Compression for y values
        TreeSet<Integer> ySet = new TreeSet<>();
        for (int num : nums2) {
            ySet.add(num);
        }
        Map<Integer, Integer> yMap = new HashMap<>();
        int rank = 0;
        for (int y : ySet) {
            yMap.put(y, rank++);
        }
        
        // Segment Tree initialization
        this.size = yMap.size();
        this.tree = new int[4 * size];
        Arrays.fill(tree, -1);

        int[] ans = new int[q];
        int pairIndex = 0;

        for (int i = 0; i < q; i++) {
            int x = indexedQueries[i][0];
            int y = indexedQueries[i][1];
            int originalIndex = indexedQueries[i][2];

            while (pairIndex < n && pairs[pairIndex][0] >= x) {
                int num1 = pairs[pairIndex][0];
                int num2 = pairs[pairIndex][1];
                int sum = num1 + num2;
                int yRank = yMap.get(num2);
                update(1, 0, size - 1, yRank, sum);
                pairIndex++;
            }

            Integer yFloor = ySet.ceiling(y);
            if (yFloor == null) {
                ans[originalIndex] = -1;
            } else {
                int yRankQuery = yMap.get(yFloor);
                ans[originalIndex] = query(1, 0, size - 1, yRankQuery, size - 1);
            }
        }
        return ans;
    }
}
```
### Algorithm
- 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`.

# Solutions
### Java

```java
class BinaryIndexedTree { private int n ; private int [] c ; public BinaryIndexedTree ( int n ) { this . n = n ; c = new int [ n + 1 ]; Arrays . fill ( c , - 1 ); } public void update ( int x , int v ) { while ( x <= n ) { c [ x ] = Math . max ( c [ x ], v ); x += x & - x ; } } public int query ( int x ) { int mx = - 1 ; while ( x > 0 ) { mx = Math . max ( mx , c [ x ]); x -= x & - x ; } return mx ; } } class Solution { public int [] maximumSumQueries ( int [] nums1 , int [] nums2 , int [][] queries ) { int n = nums1 . length ; int [][] nums = new int [ n ][ 0 ]; for ( int i = 0 ; i < n ; ++ i ) { nums [ i ] = new int [] { nums1 [ i ], nums2 [ i ]}; } Arrays . sort ( nums , ( a , b ) -> b [ 0 ] - a [ 0 ]); Arrays . sort ( nums2 ); int m = queries . length ; Integer [] idx = new Integer [ m ]; for ( int i = 0 ; i < m ; ++ i ) { idx [ i ] = i ; } Arrays . sort ( idx , ( i , j ) -> queries [ j ][ 0 ] - queries [ i ][ 0 ]); int [] ans = new int [ m ]; int j = 0 ; BinaryIndexedTree tree = new BinaryIndexedTree ( n ); for ( int i : idx ) { int x = queries [ i ][ 0 ], y = queries [ i ][ 1 ]; for (; j < n && nums [ j ][ 0 ] >= x ; ++ j ) { int k = n - Arrays . binarySearch ( nums2 , nums [ j ][ 1 ]); tree . update ( k , nums [ j ][ 0 ] + nums [ j ][ 1 ]); } int p = Arrays . binarySearch ( nums2 , y ); int k = p >= 0 ? n - p : n + p + 1 ; ans [ i ] = tree . query ( k ); } return ans ; } }
```

### CPP

```cpp
class BinaryIndexedTree { private: int n ; vector < int > c ; public: BinaryIndexedTree ( int n ) { this -> n = n ; c . resize ( n + 1 , - 1 ); } void update ( int x , int v ) { while ( x <= n ) { c [ x ] = max ( c [ x ], v ); x += x & - x ; } } int query ( int x ) { int mx = - 1 ; while ( x > 0 ) { mx = max ( mx , c [ x ]); x -= x & - x ; } return mx ; } }; class Solution { public: vector < int > maximumSumQueries ( vector < int >& nums1 , vector < int >& nums2 , vector < vector < int >>& queries ) { vector < pair < int , int >> nums ; int n = nums1 . size (), m = queries . size (); for ( int i = 0 ; i < n ; ++ i ) { nums . emplace_back ( - nums1 [ i ], nums2 [ i ]); } sort ( nums . begin (), nums . end ()); sort ( nums2 . begin (), nums2 . end ()); vector < int > idx ( m ); iota ( idx . begin (), idx . end (), 0 ); sort ( idx . begin (), idx . end (), [ & ]( int i , int j ) { return queries [ j ][ 0 ] < queries [ i ][ 0 ]; }); vector < int > ans ( m ); int j = 0 ; BinaryIndexedTree tree ( n ); for ( int i : idx ) { int x = queries [ i ][ 0 ], y = queries [ i ][ 1 ]; for (; j < n && - nums [ j ]. first >= x ; ++ j ) { int k = nums2 . end () - lower_bound ( nums2 . begin (), nums2 . end (), nums [ j ]. second ); tree . update ( k , - nums [ j ]. first + nums [ j ]. second ); } int k = nums2 . end () - lower_bound ( nums2 . begin (), nums2 . end (), y ); ans [ i ] = tree . query ( k ); } return ans ; } };
```

### Python

```python
class BinaryIndexedTree : __slots__ = [ "n" , "c" ] def __init__ ( self , n : int ): self . n = n self . c = [ - 1 ] * ( n + 1 ) def update ( self , x : int , v : int ): while x <= self . n : self . c [ x ] = max ( self . c [ x ], v ) x += x & - x def query ( self , x : int ) -> int : mx = - 1 while x : mx = max ( mx , self . c [ x ]) x -= x & - x return mx class Solution : def maximumSumQueries ( self , nums1 : List [ int ], nums2 : List [ int ], queries : List [ List [ int ]] ) -> List [ int ]: nums = sorted ( zip ( nums1 , nums2 ), key = lambda x : - x [ 0 ]) nums2 . sort () n , m = len ( nums1 ), len ( queries ) ans = [ - 1 ] * m j = 0 tree = BinaryIndexedTree ( n ) for i in sorted ( range ( m ), key = lambda i : - queries [ i ][ 0 ]): x , y = queries [ i ] while j < n and nums [ j ][ 0 ] >= x : k = n - bisect_left ( nums2 , nums [ j ][ 1 ]) tree . update ( k , nums [ j ][ 0 ] + nums [ j ][ 1 ]) j += 1 k = n - bisect_left ( nums2 , y ) ans [ i ] = tree . query ( k ) return ans
```