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 queryxi = 4andyi = 1, we can select indexj = 0sincenums1[j] >= 4andnums2[j] >= 1. The sumnums1[j] + nums2[j]is 6, and we can show that 6 is the maximum we can obtain. For the 2nd queryxi = 1andyi = 3, we can select indexj = 2sincenums1[j] >= 1andnums2[j] >= 3. The sumnums1[j] + nums2[j]is 10, and we can show that 10 is the maximum we can obtain. For the 3rd queryxi = 2andyi = 5, we can select indexj = 3sincenums1[j] >= 2andnums2[j] >= 5. The sumnums1[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 withxi= 3 andyi= 3. For every index, j, either nums1[j] <xior nums2[j] <yi. Hence, there is no solution.
Constraints:
nums1.length == nums2.length n == nums1.length 1 <= n <= 1051 <= nums1[i], nums2[i] <= 109 1 <= queries.length <= 105queries[i].length == 2xi == queries[i][1]yi == queries[i][2]1 <= xi, yi <= 109Problem Overview: You are given two arrays nums1 and nums2. For each query (x, y), select an index i such that nums1[i] >= x and nums2[i] >= y. Among all valid indices, return the maximum value of nums1[i] + nums2[i]. If no index satisfies the constraints, return -1. Each query must be answered efficiently.
Approach 1: Naive Brute Force (O(n * q) time, O(1) space)
The most direct solution checks every element for every query. For each query (x, y), iterate through all indices and test whether nums1[i] >= x and nums2[i] >= y. Track the maximum nums1[i] + nums2[i] among valid candidates. This approach uses simple iteration over the array and requires no extra data structures.
The implementation is straightforward and useful for verifying correctness on small inputs. However, it performs a full scan of the array for every query, which leads to O(n * q) time complexity. With large constraints, this becomes too slow for production or interview settings.
Approach 2: Sorting + Monotonic Stack + Binary Search (O((n + q) log n) time, O(n) space)
A faster strategy processes queries offline. First pair each index as (nums1[i], nums2[i]) and sort these pairs in descending order of nums1. Sort queries by decreasing x as well. As you process queries, gradually add all pairs with nums1 >= x into a structure.
While inserting elements, maintain a monotonic stack where nums2 values are increasing and the stored value is the best possible nums1[i] + nums2[i]. If a new pair provides a larger sum for a given or larger nums2, remove dominated entries from the stack. This keeps only candidates that could become optimal answers.
For each query, perform a binary search on the stack to find the first entry with nums2 >= y. The stored value directly gives the maximum possible sum. Sorting ensures elements are processed only once, and the monotonic structure guarantees efficient dominance pruning.
Recommended for interviews: Interviewers expect the optimized offline approach. The brute force method demonstrates you understand the constraints and baseline logic, but the sorting + monotonic stack technique shows mastery of query optimization, binary search, and advanced data structure design.
In this approach, we iterate over each query and then iterate over each index of nums1 and nums2 to check if they satisfy the conditions of that query. This is a direct implementation that checks all possibilities.
This C code performs a brute force search for each query. It iterates through each element of nums1 and nums2 to check if it satisfies the query conditions and calculates the sum if valid.
Time Complexity: O(n * m), where n is the length of nums1 and m is the number of queries.
Space Complexity: O(m), where m is the number of queries (for storing the result).
We can speed up queries by sorting the indices of nums1 and using a binary search to directly access potential matches. This reduces the time taken per query when compared to a direct search through all possible indices.
This C++ code first sorts the combined pairs of nums1 and nums2. Using lower_bound, it performs a binary search to locate potential candidates faster than linear comparison, speeding up query responses.
Time Complexity: O(n log n) for sorting, and O(m log n) per query due to binary search and partial scan.
Space Complexity: O(n) for the storage of the sorted pairs.
This problem belongs to the category of two-dimensional partial order problems.
A two-dimensional partial order problem is defined as follows: given several pairs of points (a_1, b_1), (a_2, b_2), ..., (a_n, b_n), and a defined partial order relation, now given a point (a_i, b_i), we need to find the number/maximum value of point pairs (a_j, b_j) that satisfy the partial order relation. That is:
$
\left(a_{j}, b_{j}\right) \prec\left(a_{i}, b_{i}\right) \stackrel{\text { def }}{=} a_{j} \lesseqgtr a_{i} \text { and } b_{j} \lesseqgtr b_{i}
The general solution to two-dimensional partial order problems is to sort one dimension and use a data structure to handle the second dimension (this data structure is generally a binary indexed tree).
For this problem, we can create an array nums, where nums[i]=(nums_1[i], nums_2[i]), and then sort nums in descending order according to nums_1. We also sort the queries queries in descending order according to x.
Next, we iterate through each query queries[i] = (x, y). For the current query, we loop to insert the value of nums_2 for all elements in nums that are greater than or equal to x into the binary indexed tree. The binary indexed tree maintains the maximum value of nums_1 + nums_2 in the discretized nums_2 interval. Therefore, we only need to query the maximum value corresponding to the interval greater than or equal to the discretized y in the binary indexed tree. Note that since the binary indexed tree maintains the prefix maximum value, we can insert nums_2 in reverse order into the binary indexed tree in the implementation.
The time complexity is O((n + m) times log n + m times log m), and the space complexity is O(n + m). Here, n is the length of the array nums, and m is the length of the array queries$.
Similar problems:
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Naive Brute Force Approach | Time Complexity: O(n * m), where n is the length of nums1 and m is the number of queries. |
| Optimized Approach Using Sorting and Binary Search | Time Complexity: O(n log n) for sorting, and O(m log n) per query due to binary search and partial scan. |
| Binary Indexed Tree | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Naive Brute Force | O(n * q) | O(1) | Useful for small inputs or validating logic during development |
| Sorting + Monotonic Stack + Binary Search | O((n + q) log n) | O(n) | Best general solution for large constraints and interview settings |
Hardest Idea on Leetcode? | Leetcode Weekly Episode 8 | Leetcode 2736 | Vivek Gupta • Vivek Gupta • 4,766 views views
Watch 7 more video solutions →Practice Maximum Sum Queries with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor