Skip to content

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

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:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class BinaryIndexedTree {
    private int n;
    private int[] c;

    public BinaryIndexedTree(int n) {
        this.n = n;
        c = new int[n + 1];
        Arrays.fill(c, -1);
    }

    public void update(int x, int v) {
        while (x <= n) {
            c[x] = Math.max(c[x], v);
            x += x & -x;
        }
    }

    public int query(int x) {
        int mx = -1;
        while (x > 0) {
            mx = Math.max(mx, c[x]);
            x -= x & -x;
        }
        return mx;
    }
}

class Solution {
    public int[] maximumSumQueries(int[] nums1, int[] nums2, int[][] queries) {
        int n = nums1.length;
        int[][] nums = new int[n][0];
        for (int i = 0; i < n; ++i) {
            nums[i] = new int[] {nums1[i], nums2[i]};
        }
        Arrays.sort(nums, (a, b) -> b[0] - a[0]);
        Arrays.sort(nums2);
        int m = queries.length;
        Integer[] idx = new Integer[m];
        for (int i = 0; i < m; ++i) {
            idx[i] = i;
        }
        Arrays.sort(idx, (i, j) -> queries[j][0] - queries[i][0]);
        int[] ans = new int[m];
        int j = 0;
        BinaryIndexedTree tree = new BinaryIndexedTree(n);
        for (int i : idx) {
            int x = queries[i][0], y = queries[i][1];
            for (; j < n && nums[j][0] >= x; ++j) {
                int k = n - Arrays.binarySearch(nums2, nums[j][1]);
                tree.update(k, nums[j][0] + nums[j][1]);
            }
            int p = Arrays.binarySearch(nums2, y);
            int k = p >= 0 ? n - p : n + p + 1;
            ans[i] = tree.query(k);
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
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;
}

We process queries in descending order of their corresponding \(x\) threshold. At the same time, we also sort number pairs in descending order of \(\textit{nums1}[i]\).

For each \(query_j\), all number pairs satisfying \(\textit{nums1}[i] \geq x_j\) are added to a monotonic stack.

Such a stack runs in ascending order of \(\textit{nums2}[i]\) but descending order of \(\textit{nums1}[i] + \textit{nums2}[i]\), ensuring that any candidate with a larger \(\textit{nums2}[i]\) has a smaller \(\textit{nums1}[i] + \textit{nums2}[i]\) instead, so only effective candidates are kept.

For each \(query_j\), binary search locates the first stack entry having \(\textit{nums2}[i] \geq y_j\). Its corresponding \(\textit{nums1}[i] + \textit{nums2}[i]\) is the answer.

Time & Space Complexity

Here, \(n\) is the length of array \(nums2\), and \(m\) is the length of array \(queries\).

  • Time complexity: \(O((n + m) \times \log n + m \times \log m)\)。
  • Space complexity: \(O(n + m)\)。
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution:
    def maximumSumQueries(
        self, nums1: list[int], nums2: list[int], queries: list[list[int]]
    ) -> list[int]:
        max_values = [-1] * len(queries)

        queries = [(query[0], query[1], idx) for idx, query in enumerate(queries)]
        # Process queries by descending x threshold and y threshold.
        queries.sort(key=lambda x: (-x[0], -x[1]))

        tuples: list[tuple[int, int]] = []  # Format: (num 1, num 2).
        for num_1, num_2 in zip(nums1, nums2):
            tuples.append((num_1, num_2))

        # Process queries by descending num 1 and num 2.
        # Sort by ascending num 1 and num 2 to pop from the back.
        tuples.sort(key=lambda x: (x[0], x[1]))

        stack: list[tuple[int, int]] = []  # Format: (num 2, sum).

        for query_1, query_2, query_idx in queries:
            while tuples and tuples[-1][0] >= query_1:  # Tuple's num 1 >= x threshold.
                num_1, num_2 = tuples.pop(-1)
                nums_sum = num_1 + num_2

                while stack and stack[-1][0] < num_2 and stack[-1][1] <= nums_sum:
                    stack.pop(-1)  # Stack top isn't better than popped tuple.

                insertion_idx = bisect_left(stack, (num_2, nums_sum))

                if insertion_idx == len(stack):
                    stack.insert(insertion_idx, (num_2, nums_sum))

                elif stack[insertion_idx][1] < nums_sum:
                    stack.insert(insertion_idx, (num_2, nums_sum))

            search_idx = bisect_left(stack, (query_2, 0))
            if search_idx < len(stack):
                max_values[query_idx] = stack[search_idx][1]

        return max_values

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
public:
    vector<int> maximumSumQueries(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& queries) {
        vector<int> maxValues(queries.size(), -1);

        vector<vector<int>> queriesIndices;
        for (int idx = 0; idx < queries.size(); idx++)
            queriesIndices.push_back({queries[idx][0], queries[idx][1], idx});

        // Process queries by descending x threshold and y threshold.
        // Sort ascendingly and later pop from the back.
        sort(queriesIndices.begin(), queriesIndices.end());

        vector<pair<int, int>> numsPairs; // Format: {num 1, num 2}.
        for (int idx = 0; idx < nums2.size(); idx++)
            numsPairs.push_back({nums1[idx], nums2[idx]});

        // Process queries by descending num 1 and num 2.
        // Sort by ascending num 1 and num 2 to pop from the back.
        sort(numsPairs.begin(), numsPairs.end());

        deque<pair<int, int>> stack; // Format: {num 2, sum}.

        while (!queriesIndices.empty()) {
            int queryOne = queriesIndices.back()[0];
            int queryTwo = queriesIndices.back()[1];
            int queryIdx = queriesIndices.back()[2];
            queriesIndices.pop_back();

            // Pair's num 1 >= x threshold.
            while (!numsPairs.empty() && numsPairs.back().first >= queryOne) {
                auto [numOne, numTwo] = numsPairs.back();
                numsPairs.pop_back();
                int numsSum = numOne + numTwo;

                while (!stack.empty() and stack.back().first < numTwo and stack.back().second <= numsSum)
                    stack.pop_back(); // Stack top isn't better than popped pair.

                pair<int, int> targetPair = {numTwo, numsSum};
                int insertion_idx = lower_bound(stack.begin(), stack.end(), targetPair) - stack.begin();

                if (insertion_idx == stack.size())
                    stack.insert(stack.begin() + insertion_idx, targetPair);

                else if (stack[insertion_idx].second < numsSum)
                    stack.insert(stack.begin() + insertion_idx, targetPair);
            }

            pair<int, int> queryNumTwoPair = {queryTwo, 0};

            int search_idx = lower_bound(stack.begin(), stack.end(), queryNumTwoPair) - stack.begin();
            if (search_idx < stack.size())
                maxValues[queryIdx] = stack[search_idx].second;
        }

        return maxValues;
    }
};

Comments