Welcome to Subscribe On Youtube
2736. Maximum Sum Queries
Description
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
Solutions
Solution 1: 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 Solution { public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] q) { int n = nums1.length, m = q.length; int[][] a = new int[n][2]; for (int i = 0; i < n; i++) { a[i][0] = nums1[i]; a[i][1] = nums2[i]; } int[][] b = new int[m][3]; for (int i = 0; i < m; i++) { b[i][0] = q[i][0]; b[i][1] = q[i][1]; b[i][2] = i; } Arrays.sort(a, (o1, o2) -> o1[0] - o2[0]); Arrays.sort(b, (o1, o2) -> o1[0] - o2[0]); TreeMap<Integer, Integer> map = new TreeMap<>(); int[] res = new int[m]; int max = -1; for (int i = m - 1, j = n - 1; i >= 0; i--) { int x = b[i][0], y = b[i][1], idx = b[i][2]; while (j >= 0 && a[j][0] >= x) { if (max < a[j][1]) { max = a[j][1]; Integer key = map.floorKey(a[j][1]); while (key != null && map.get(key) <= a[j][0] + a[j][1]) { map.remove(key); key = map.floorKey(key); } map.put(max, a[j][0] + a[j][1]); } j--; } Integer key = map.ceilingKey(y); if (key == null) res[idx] = -1; else res[idx] = map.get(key); } return res; } } -
class BinaryIndexedTree { private: int n; vector<int> c; public: BinaryIndexedTree(int n) { this->n = n; c.resize(n + 1, -1); } void update(int x, int v) { while (x <= n) { c[x] = max(c[x], v); x += x & -x; } } int query(int x) { int mx = -1; while (x > 0) { mx = max(mx, c[x]); x -= x & -x; } return mx; } }; class Solution { public: vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) { vector<pair<int, int>> nums; int n = nums1.size(), m = queries.size(); for (int i = 0; i < n; ++i) { nums.emplace_back(-nums1[i], nums2[i]); } sort(nums.begin(), nums.end()); sort(nums2.begin(), nums2.end()); vector<int> idx(m); iota(idx.begin(), idx.end(), 0); sort(idx.begin(), idx.end(), [&](int i, int j) { return queries[j][0] < queries[i][0]; }); vector<int> ans(m); int j = 0; BinaryIndexedTree tree(n); for (int i : idx) { int x = queries[i][0], y = queries[i][1]; for (; j < n && -nums[j].first >= x; ++j) { int k = nums2.end() - lower_bound(nums2.begin(), nums2.end(), nums[j].second); tree.update(k, -nums[j].first + nums[j].second); } int k = nums2.end() - lower_bound(nums2.begin(), nums2.end(), y); ans[i] = tree.query(k); } return ans; } }; -
class BinaryIndexedTree: __slots__ = ["n", "c"] def __init__(self, n: int): self.n = n self.c = [-1] * (n + 1) def update(self, x: int, v: int): while x <= self.n: self.c[x] = max(self.c[x], v) x += x & -x def query(self, x: int) -> int: mx = -1 while x: mx = max(mx, self.c[x]) x -= x & -x return mx class Solution: def maximumSumQueries( self, nums1: List[int], nums2: List[int], queries: List[List[int]] ) -> List[int]: nums = sorted(zip(nums1, nums2), key=lambda x: -x[0]) nums2.sort() n, m = len(nums1), len(queries) ans = [-1] * m j = 0 tree = BinaryIndexedTree(n) for i in sorted(range(m), key=lambda i: -queries[i][0]): x, y = queries[i] while j < n and nums[j][0] >= x: k = n - bisect_left(nums2, nums[j][1]) tree.update(k, nums[j][0] + nums[j][1]) j += 1 k = n - bisect_left(nums2, 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 } -
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; }