#2736

Hard

auto_awesomeBinary search over the valid answer space

LeetCode Problem Workspace

Maximum Sum Queries

Find the maximum sum of paired elements from two arrays under query constraints using efficient binary search techniques.

array binary search stack binary indexed tree segment tree

Problem Statement

You are given two integer arrays nums1 and nums2 of length n, and a list of queries where each query contains two integers [xi, yi]. For each query, find the maximum sum nums1[j] + nums2[j] among all indices j such that nums1[j] >= xi and nums2[j] >= yi.

If no index satisfies the constraints for a query, return -1 for that query. Output an array answer where answer[i] corresponds to the ith query's maximum sum.

Examples

Example 1

Input: nums1 = [4,3,1,2], nums2 = [2,4,9,5], queries = [[4,1],[1,3],[2,5]]

Output: [6,10,7]

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]

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]

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

Solution Approach

Sort and Preprocess

Sort the array of pairs (nums1[i], nums2[i]) by nums1 descending. Sort queries by xi descending, and track original indices to fill the answer array efficiently.

Use Binary Search Over Valid Sums

For each query, perform binary search on the preprocessed nums1 array to find candidate indices satisfying nums1[j] >= xi. Maintain a structure like a segment tree or monotonic stack to quickly retrieve the maximum nums2[j] for the current range.

Update Answers Efficiently

Iterate through queries and update the maximum sums dynamically as you progress. For each query, check if there exists a valid nums2[j] >= yi and record nums1[j] + nums2[j] or -1 if none satisfy.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on sorting arrays and queries O(n log n + q log n) and segment tree updates, while space complexity depends on storing the preprocessed pairs and segment tree structures.

What Interviewers Usually Probe

Sorting pairs and queries indicates efficient precomputation.
Binary search over nums1 for each query shows pattern recognition of valid answer space.
Using segment tree or monotonic stack shows candidate max sum tracking skill.

Common Pitfalls or Variants

Common pitfalls

Not indexing queries before sorting can misalign answers.
Scanning all elements for each query leads to TLE on large inputs.
Forgetting to handle the -1 case when no elements satisfy the constraints.

Follow-up variants

Compute minimum sum under similar constraints instead of maximum.
Extend to 3D arrays or additional dimensions with threshold constraints.
Allow updates to nums1 or nums2 between queries and recompute efficiently.

FAQ

What is the main pattern used in Maximum Sum Queries?

The key pattern is binary search over the valid answer space combined with pre-sorted arrays for efficient query handling.

How do I handle queries that have no valid indices?

Return -1 for any query where no index j satisfies both nums1[j] >= xi and nums2[j] >= yi.

Why use a segment tree or monotonic stack?

These structures allow efficient retrieval of the maximum nums2[j] for the filtered nums1[j] indices without scanning all elements.

Can this approach handle large arrays and many queries?

Yes, sorting and using binary search plus segment trees reduce time complexity to O(n log n + q log n), suitable for n and q up to 10^5.

Do queries need to be processed in input order?

No, they can be sorted by xi descending for efficient processing but answers must be returned in the original query order.

terminal

Solution

Solution 1: Binary Indexed Tree

This problem belongs to the category of two-dimensional partial order problems.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

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

Continue Practicing

#2940 find building where alice and bob can meet #2659 make array empty #2454 next greater element iv