2736. Maximum Sum Queries LeetCode Solution
In this guide, you will get 2736. Maximum Sum Queries LeetCode Solution with the best time and space complexity. The solution to Maximum Sum Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Table of Contents
- Problem Statement
- Complexity Analysis
- Maximum Sum Queries solution in C++
- Maximum Sum Queries solution in Java
- Maximum Sum Queries solution in Python
- Additional Resources
Problem Statement of Maximum Sum Queries
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 = 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 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]
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 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
Complexity Analysis
- Time Complexity: O(\texttt{sort}(n) + \texttt{sort}(q) + (q + n)\log n)
- Space Complexity: O(n + q)
2736. Maximum Sum Queries LeetCode Solution in C++
struct Pair {
int x;
int y;
};
struct IndexedQuery {
int queryIndex;
int minX;
int minY;
};
class Solution {
public:
vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2,
vector<vector<int>>& queries) {
const vector<Pair> pairs = getPairs(nums1, nums2);
vector<int> ans(queries.size());
vector<pair<int, int>> stack; // [(y, x + y)]
int pairsIndex = 0;
for (const auto& [queryIndex, minX, minY] : getIndexedQueries(queries)) {
while (pairsIndex < pairs.size() && pairs[pairsIndex].x >= minX) {
const auto [x, y] = pairs[pairsIndex++];
// x + y is a better candidate. Given that x is decreasing, the
// condition "x + y >= stack.back().second" suggests that y is
// relatively larger, thereby making it a better candidate.
while (!stack.empty() && x + y >= stack.back().second)
stack.pop_back();
if (stack.empty() || y > stack.back().first)
stack.emplace_back(y, x + y);
}
const auto it = ranges::lower_bound(stack, pair<int, int>{minY, INT_MIN});
ans[queryIndex] = it == stack.end() ? -1 : it->second;
}
return ans;
}
private:
vector<Pair> getPairs(const vector<int>& nums1, const vector<int>& nums2) {
vector<Pair> pairs;
for (int i = 0; i < nums1.size(); ++i)
pairs.push_back({nums1[i], nums2[i]});
ranges::sort(pairs, ranges::greater{},
[](const Pair& pair) { return pair.x; });
return pairs;
}
vector<IndexedQuery> getIndexedQueries(const vector<vector<int>>& queries) {
vector<IndexedQuery> indexedQueries;
for (int i = 0; i < queries.size(); ++i)
indexedQueries.push_back({i, queries[i][0], queries[i][1]});
ranges::sort(indexedQueries,
[](const IndexedQuery& a, const IndexedQuery& b) {
return a.minX > b.minX;
});
return indexedQueries;
}
};
/* code provided by PROGIEZ */2736. Maximum Sum Queries LeetCode Solution in Java
class Solution {
public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
MyPair[] pairs = getPairs(nums1, nums2);
IndexedQuery[] indexedQueries = getIndexedQueries(queries);
int[] ans = new int[queries.length];
List<Pair<Integer, Integer>> stack = new ArrayList<>(); // [(y, x + y)]
int pairsIndex = 0;
for (IndexedQuery indexedQuery : indexedQueries) {
final int queryIndex = indexedQuery.queryIndex;
final int minX = indexedQuery.minX;
final int minY = indexedQuery.minY;
while (pairsIndex < pairs.length && pairs[pairsIndex].x >= minX) {
MyPair pair = pairs[pairsIndex++];
// x + y is a better candidate. Given that x is decreasing, the
// condition "x + y >= stack.get(stack.size() - 1).getValue()" suggests
// that y is relatively larger, thereby making it a better candidate.
final int x = pair.x;
final int y = pair.y;
while (!stack.isEmpty() && x + y >= stack.get(stack.size() - 1).getValue())
stack.remove(stack.size() - 1);
if (stack.isEmpty() || y > stack.get(stack.size() - 1).getKey())
stack.add(new Pair<>(y, x + y));
}
final int j = firstGreaterEqual(stack, minY);
ans[queryIndex] = j == stack.size() ? -1 : stack.get(j).getValue();
}
return ans;
}
private record MyPair(int x, int y){};
private record IndexedQuery(int queryIndex, int minX, int minY){};
private int firstGreaterEqual(List<Pair<Integer, Integer>> A, int target) {
int l = 0;
int r = A.size();
while (l < r) {
final int m = (l + r) / 2;
if (A.get(m).getKey() >= target)
r = m;
else
l = m + 1;
}
return l;
}
private MyPair[] getPairs(int[] nums1, int[] nums2) {
MyPair[] pairs = new MyPair[nums1.length];
for (int i = 0; i < nums1.length; ++i)
pairs[i] = new MyPair(nums1[i], nums2[i]);
Arrays.sort(pairs, (a, b) -> Integer.compare(b.x, a.x));
return pairs;
}
private IndexedQuery[] getIndexedQueries(int[][] queries) {
IndexedQuery[] indexedQueries = new IndexedQuery[queries.length];
for (int i = 0; i < queries.length; ++i)
indexedQueries[i] = new IndexedQuery(i, queries[i][0], queries[i][1]);
Arrays.sort(indexedQueries, (a, b) -> Integer.compare(b.minX, a.minX));
return indexedQueries;
}
}
// code provided by PROGIEZ2736. Maximum Sum Queries LeetCode Solution in Python
from dataclasses import dataclass
@dataclass(frozen=True)
class Pair:
x: int
y: int
def __iter__(self):
yield self.x
yield self.y
@dataclass(frozen=True)
class IndexedQuery:
queryIndex: int
minX: int
minY: int
def __iter__(self):
yield self.queryIndex
yield self.minX
yield self.minY
class Solution:
def maximumSumQueries(
self,
nums1: list[int],
nums2: list[int],
queries: list[list[int]],
) -> list[int]:
pairs = sorted([Pair(nums1[i], nums2[i])
for i in range(len(nums1))], key=lambda x: x.x, reverse=True)
ans = [0] * len(queries)
stack = [] # [(y, x + y)]
pairsIndex = 0
for queryIndex, minX, minY in sorted([IndexedQuery(i, query[0], query[1])
for i, query in enumerate(queries)],
key=lambda x: -x.minX):
while pairsIndex < len(pairs) and pairs[pairsIndex].x >= minX:
# x + y is a better candidate. Given that x is decreasing, the
# condition "x + y >= stack[-1][1]" suggests that y is relatively
# larger, thereby making it a better candidate.
x, y = pairs[pairsIndex]
while stack and x + y >= stack[-1][1]:
stack.pop()
if not stack or y > stack[-1][0]:
stack.append((y, x + y))
pairsIndex += 1
j = self._firstGreaterEqual(stack, minY)
ans[queryIndex] = -1 if j == len(stack) else stack[j][1]
return ans
def _firstGreaterEqual(self, A: list[tuple[int, int]], target: int) -> int:
l = 0
r = len(A)
while l < r:
m = (l + r) // 2
if A[m][0] >= target:
r = m
else:
l = m + 1
return l
# code by PROGIEZAdditional Resources
- Explore all LeetCode problem solutions at Progiez here
- Explore all problems on LeetCode website here
Happy Coding! Keep following PROGIEZ for more updates and solutions.