Maximum Sum Queries solution and explanation
7 more videos on this problem
Hardest Idea on Leetcode? | Leetcode Weekly Episode 8 | Leetcode 2736 | Vivek GuptaVivek Gupta · 19:16 · 4K views
6473. Maximum Sum Queries | Merge Sort Trees | Segment Tree | Leetcode Weekly Contest 349codingMohan · 50:15 · 1K views
Leetcode Weekly 349 : 6473. Maximum Sum QueriesDivyansh Tyagi · 26:35 · 1K views
Leetcode Weekly contest 349 - Hard - Maximum Sum QueriesPrakhar Agrawal · 37:22 · 976 views
2736. Maximum Sum Queries (Leetcode Hard)Programming Live with Larry · 45:33 · 673 views
【每日一题】LeetCode 2736. Maximum Sum QueriesHuifeng Guan · 29:51 · 511 views
Maximum Sum Queries - LeetCode 2736 - PythonAlpha-Code · 44:21 · 219 views
Mastering Maximum Sum Queries: LeetCode 2736 - Weekly Contest 349 TutorialvanAmsen · 14:09 · 146 views
The problem
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.lengthn == nums1.length1 <= n <= 1051 <= nums1[i], nums2[i] <= 1091 <= queries.length <= 105queries[i].length == 2xi == queries[i][1]yi == queries[i][2]1 <= xi, yi <= 109
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.
def maximumSumQueries(nums1, nums2, queries):
n = len(nums1)
result = []
for x, y in queries:
max_sum = -1
for j in range(n):
if nums1[j] >= x and nums2[j] >= y:
max_sum = max(max_sum, nums1[j] + nums2[j])
result.append(max_sum)
return resultimport java.util.ArrayList;
import java.util.List;
public class Solution {
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.length;
int[] answer = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int xi = queries[i][0];
int yi = queries[i][1];
int maxSum = -1;
for (int j = 0; j < n; j++) {
if (nums1[j] >= xi && nums2[j] >= yi) {
maxSum = Math.max(maxSum, nums1[j] + nums2[j]);
}
}
answer[i] = maxSum;
}
return answer;
}
}#include <vector>
using namespace std;
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums1.size();
vector<int> answer;
for (auto& q : queries) {
int xi = q[0];
int yi = q[1];
int maxSum = -1;
for (int j = 0; j < n; ++j) {
if (nums1[j] >= xi && nums2[j] >= yi) {
maxSum = max(maxSum, nums1[j] + nums2[j]);
}
}
answer.push_back(maxSum);
}
return answer;
}function maximumSumQueries(nums1, nums2, queries) {
const result = [];
for (const [xi, yi] of queries) {
let maxSum = -1;
for (let j = 0; j < nums1.length; j++) {
if (nums1[j] >= xi && nums2[j] >= yi) {
maxSum = Math.max(maxSum, nums1[j] + nums2[j]);
}
}
result.push(maxSum);
}
return result;
}#include <stdio.h>
#include <stdlib.h>
int* maximumSumQueries(int* nums1, int nums1Size, int* nums2, int nums2Size, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
*returnSize = queriesSize;
int* answer = (int*)malloc(sizeof(int) * queriesSize);
for (int i = 0; i < queriesSize; ++i) {
int xi = queries[i][0];
int yi = queries[i][1];
int maxSum = -1;
for (int j = 0; j < nums1Size; ++j) {
if (nums1[j] >= xi && nums2[j] >= yi) {
int sum = nums1[j] + nums2[j];
if (sum > maxSum) {
maxSum = sum;
}
}
}
answer[i] = maxSum;
}
return answer;
}using System;
using System.Collections.Generic;
public class Solution {
public int[] MaximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.Length;
int[] answer = new int[queries.Length];
for (int i = 0; i < queries.Length; i++) {
int xi = queries[i][0];
int yi = queries[i][1];
int maxSum = -1;
for (int j = 0; j < n; j++) {
if (nums1[j] >= xi && nums2[j] >= yi) {
maxSum = Math.Max(maxSum, nums1[j] + nums2[j]);
}
}
answer[i] = maxSum;
}
return answer;
}
}The Python approach follows the brute-force pattern, iterating through `nums1` and `nums2` to find valid indices for each query and computing the maximum possible sum.
Time Complexity: O(n * m), where n is the size of nums1 and m is the number of queries.
Space Complexity: O(m) for storing results.
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.
def maximumSumQueries(nums1, nums2, queries):
num_pairs = sorted(zip(nums1, nums2))
result = []
for x, y in queries:
max_sum = -1
for nx, ny in num_pairs:
if nx >= x and ny >= y:
max_sum = max(max_sum, nx + ny)
result.append(max_sum)
return resultimport java.util.*;
public class Solution {
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
int n = nums1.length;
List<int[]> numPairs = new ArrayList<>();
for (int i = 0; i < n; i++) {
numPairs.add(new int[]{nums1[i], nums2[i]});
}
numPairs.sort((a, b) -> Integer.compare(a[0], b[0]));
int[] answer = new int[queries.length];
for (int i = 0; i < queries.length; i++) {
int xi = queries[i][0];
int yi = queries[i][1];
int maxSum = -1;
for (int[] pair : numPairs) {
if (pair[0] >= xi && pair[1] >= yi) {
maxSum = Math.max(maxSum, pair[0] + pair[1]);
}
}
answer[i] = maxSum;
}
return answer;
}
}#include <vector>
#include <algorithm>
using namespace std;
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
int n = nums1.size();
vector<pair<int, int>> num_pairs(n);
for (int i = 0; i < n; ++i) {
num_pairs[i] = {nums1[i], nums2[i]};
}
sort(num_pairs.begin(), num_pairs.end());
vector<int> answer;
for (auto& q : queries) {
int xi = q[0];
int yi = q[1];
int maxSum = -1;
// Binary search to find bounds in sorted array
auto it = lower_bound(num_pairs.begin(), num_pairs.end(), make_pair(xi, yi));
for (auto itr = it; itr != num_pairs.end(); ++itr) {
if (itr->second >= yi) {
maxSum = max(maxSum, itr->first + itr->second);
}
}
answer.push_back(maxSum);
}
return answer;
}This Python implementation sorts the zipped pairs of inputs and iterates over queries, leveraging sorted order for potentially quicker valid range checks when possible.
Time Complexity: O(n log n) to sort pairs and O(m * n) in the worst-case for directly checking sorted elements.
Space Complexity: O(n) for the list of tuples.
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$.
Similar problems:
class BinaryIndexedTree {
private n: number;
private c: number[];
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(-1);
}
update(x: number, v: number): void {
while (x <= this.n) {
this.c[x] = Math.max(this.c[x], v);
x += x & -x;
}
}
query(x: number): number {
let mx = -1;
while (x > 0) {
mx = Math.max(mx, this.c[x]);
x -= x & -x;
}
return mx;
}
}
function maximumSumQueries(nums1: number[], nums2: number[], queries: number[][]): number[] {
const n = nums1.length;
const m = queries.length;
const nums: [number, number][] = [];
for (let i = 0; i < n; ++i) {
nums.push([nums1[i], nums2[i]]);
}
nums.sort((a, b) => b[0] - a[0]);
nums2.sort((a, b) => a - b);
const idx: number[] = Array(m)
.fill(0)
.map((_, i) => i);
idx.sort((i, j) => queries[j][0] - queries[i][0]);
const ans: number[] = Array(m).fill(0);
let j = 0;
const search = (x: number) => {
let [l, r] = [0, n];
while (l < r) {
const mid = (l + r) >> 1;
if (nums2[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
const tree = new BinaryIndexedTree(n);
for (const i of idx) {
const [x, y] = queries[i];
for (; j < n && nums[j][0] >= x; ++j) {
const k = n - search(nums[j][1]);
tree.update(k, nums[j][0] + nums[j][1]);
}
const k = n - search(y);
ans[i] = tree.query(k);
}
return ans;
}type BinaryIndexedTree struct {
n int
c []int
}
func NewBinaryIndexedTree(n int) BinaryIndexedTree {
c := make([]int, n+1)
for i := range c {
c[i] = -1
}
return BinaryIndexedTree{n: n, c: c}
}
func (bit *BinaryIndexedTree) update(x, v int) {
for x <= bit.n {
bit.c[x] = max(bit.c[x], v)
x += x & -x
}
}
func (bit *BinaryIndexedTree) query(x int) int {
mx := -1
for x > 0 {
mx = max(mx, bit.c[x])
x -= x & -x
}
return mx
}
func maximumSumQueries(nums1 []int, nums2 []int, queries [][]int) []int {
n, m := len(nums1), len(queries)
nums := make([][2]int, n)
for i := range nums {
nums[i] = [2]int{nums1[i], nums2[i]}
}
sort.Slice(nums, func(i, j int) bool { return nums[j][0] < nums[i][0] })
sort.Ints(nums2)
idx := make([]int, m)
for i := range idx {
idx[i] = i
}
sort.Slice(idx, func(i, j int) bool { return queries[idx[j]][0] < queries[idx[i]][0] })
tree := NewBinaryIndexedTree(n)
ans := make([]int, m)
j := 0
for _, i := range idx {
x, y := queries[i][0], queries[i][1]
for ; j < n && nums[j][0] >= x; j++ {
k := n - sort.SearchInts(nums2, nums[j][1])
tree.update(k, nums[j][0]+nums[j][1])
}
k := n - sort.SearchInts(nums2, y)
ans[i] = tree.query(k)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Naive Brute Force Approach | Time Complexity: O(n * m), where n is the size of nums1 and m is the number of queries. |
| Optimized Approach Using Sorting and Binary Search | Time Complexity: O(n log n) to sort pairs and O(m * n) in the worst-case for directly checking sorted elements. |
| Binary Indexed Tree | – |
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 |
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.