Maximum Sum Queries - Solution & Explanation

HardArray Binary Search Stack Binary Indexed Tree21 min read

Problem Statement

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] = [x_i, y_i].

For the i^th query, find the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n), where nums1[j] >= x_i and nums2[j] >= y_i, or -1 if there is no j satisfying the constraints.

Return an array answer where answer[i] is the answer to the i^th 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 x_i = 4 and y_i = 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 x_i = 1 and y_i = 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 x_i = 2 and y_i = 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 x_i = 3 and y_i = 3. For every index, j, either nums1[j] < x_i or nums2[j] < y_i. Hence, there is no solution.

Constraints:

nums1.length == nums2.length
n == nums1.length
1 <= n <= 10⁵
1 <= nums1[i], nums2[i] <= 10⁹
1 <= queries.length <= 10⁵
queries[i].length == 2
x_i == queries[i][1]
y_i == queries[i][2]
1 <= x_i, y_i <= 10⁹

Approach Overview

Problem 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 1: Naive Brute Force Approach

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.

Code

C C++Java Python C#JavaScript

C++

Java

Python

JavaScript

Complexity

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).

Try this approach in the editor →

Approach 2: Optimized Approach Using Sorting and Binary Search

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.

Code

C++Java Python

C++

Java

Python

Complexity

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.

Try this approach in the editor →

Approach 3: Binary Indexed Tree

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$.

Code

Python Java C++Go TypeScript

Python

Java

C++

TypeScript

Try this approach in the editor →

Complexity Comparison

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. Space Complexity: O(m), where m is the number of queries (for storing the result).
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. Space Complexity: O(n) for the storage of the sorted pairs.
Binary Indexed Tree	—

Detailed Complexity Analysis

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

Video Solution

Hardest Idea on Leetcode? | Leetcode Weekly Episode 8 | Leetcode 2736 | Vivek Gupta • Vivek Gupta • 4,909 views views

Watch 7 more video solutions →

Frequently Asked Questions

Is Maximum Sum Queries easy or hard?

Maximum Sum Queries is classified as Hard because it combines multiple advanced ideas: offline query processing, dominance pruning with a monotonic stack, and binary search over dynamically maintained candidates.

Maximum Sum Queries Python/Java solution

The typical Python or Java solution sorts pairs and queries, maintains a monotonic stack of candidate (nums2, nums1+nums2) values, and performs binary search to answer each query. This approach runs in O((n + q) log n) time and uses O(n) extra space.

What is the best approach for Maximum Sum Queries?

The most efficient approach processes queries offline using sorting, a monotonic stack, and binary search. Sort pairs by nums1 and queries by x in descending order, then insert candidates while maintaining a stack that keeps only optimal (nums2, sum) pairs. Each query is answered with binary search on the stack, resulting in O((n + q) log n) time complexity.

Is Maximum Sum Queries asked at Google/Amazon/Meta?

Problems combining offline queries, monotonic stacks, and binary search frequently appear in interviews at companies like Google, Amazon, and Meta. Maximum Sum Queries tests your ability to optimize query processing and manage dominance relationships between candidates.

What data structure is used in Maximum Sum Queries?

The optimized solution uses sorting, a monotonic stack to remove dominated candidates, and binary search to answer queries efficiently. Some alternative implementations also use segment trees or binary indexed trees to manage range maximum queries.

What is the time complexity of Maximum Sum Queries?

The brute force approach runs in O(n * q) time because each query scans the entire array. The optimized method uses sorting and binary search with a monotonic stack, achieving O((n + q) log n) time and O(n) space.

How to solve Maximum Sum Queries in O((n + q) log n)?

Sort the (nums1[i], nums2[i]) pairs in decreasing order of nums1 and sort queries by x in the same order. As queries are processed, insert valid pairs into a monotonic stack that keeps increasing nums2 values with their best sums. Use binary search on the stack to find the first nums2 >= y and return the stored maximum sum.

Ready to solve this problem?

Practice Maximum Sum Queries with our built-in code editor and test cases.

Practice on FleetCode

Most Beautiful Item for Each Query

Problem Info

DifficultyHard

Acceptance31.2%

Approaches3

Reading time21 min

Practice this problem

Open in Editor

Problem Statement

Approach Overview

Approach 1: Naive Brute Force Approach

Code

Complexity

Approach 2: Optimized Approach Using Sorting and Binary Search

Code

Complexity

Approach 3: Binary Indexed Tree

Code

Complexity Comparison

Detailed Complexity Analysis

Video Solution

Frequently Asked Questions

Related Problems

Ready to solve this problem?

Problem Info

Table of Contents