Watch 8 video solutions for Maximum Sum Queries, a hard level problem involving Array, Binary Search, Stack. This walkthrough by Vivek Gupta has 4,766 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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 |