How to Solve Maximum Sum Queries

Start by sorting nums1 and nums2 along with their indices to allow fast filtering by query constraints. For each query, use binary search over the nums1 values and track nums2 values using a segment tree or monotonic stack. This ensures each query returns the maximum nums1[j] + nums2[j] efficiently without scanning all elements.

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

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.

How GhostInterview Helps

• Automatically sorts and preprocesses arrays for query-based maximum sum calculations.
• Applies binary search and segment tree logic to answer each query correctly.
• Highlights common pitfalls like missing -1 cases or misaligned indices during processing.

Topic Pages

• Array
• Binary Search
• Stack
• Binary Indexed Tree
• Segment Tree
• Sorting
• Monotonic Stack

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

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.