LeetCode Solutions Blog

Maximum Sum Queries

Number: 2839

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

Given two 0-indexed integer arrays nums1 and nums2 (both of length n) and a 1-indexed 2D array queries, where each query is represented as [x, y], the goal is to find for each query the maximum value of nums1[j] + nums2[j] among all indices j (0 <= j < n) satisfying nums1[j] >= x and nums2[j] >= y. If no such index exists, return -1 for that query.

Key Insights

Process queries offline by sorting them according to the first condition (x) in descending order.
Similarly, sort the array entries (points) by their nums1 values (also descending) so that when processing a query you can quickly pick all candidate indices.
Use coordinate compression on nums2 to make it feasible to build an efficient data structure.
A Fenwick Tree (Binary Indexed Tree) or Segment Tree is employed to maintain and query the maximum sum for points that satisfy the second condition (nums2 >= y).
Each query then uses a range query on the data structure to decide the result.

Space and Time Complexity

Time Complexity: O((n + q) log n), where n = length of nums arrays and q = number of queries.
Space Complexity: O(n) to store the BIT/Segment Tree plus extra space for sorting/coordinate compression.

Solution

The solution works by processing both the data points and the queries in descending order by their nums1 or query x value. For each query [x, y]:

Add all points with nums1 >= x into a data structure keyed by their compressed nums2 value. Each point holds its sum = nums1 + nums2.
Use the data structure (BIT or Segment Tree) to query the maximum sum for indices whose corresponding nums2 values (after compression) are >= y.
Record the result, or -1 if the query yields no valid point. Coordinate compression is used for nums2 values to build a BIT/Segment Tree efficiently, ensuring updates and queries in O(log n).

Code Solutions

# Python solution using a Binary Indexed Tree (Fenwick Tree)
class FenwickTree:
    def __init__(self, size):
        self.size = size
        self.data = [float('-inf')] * (size + 1)  # 1-indexed BIT structure

    def update(self, i, value):
        # Update index i with the maximum value
        while i <= self.size:
            self.data[i] = max(self.data[i], value)
            i += i & -i

    def query(self, i):
        # Query range [1, i] for the maximum value
        result = float('-inf')
        while i > 0:
            result = max(result, self.data[i])
            i -= i & -i
        return result

def maximumSumQueries(nums1, nums2, queries):
    n = len(nums1)
    points = []
    for i in range(n):
        points.append((nums1[i], nums2[i], nums1[i] + nums2[i]))
    # Sort points based on nums1 descending
    points.sort(key=lambda x: x[0], reverse=True)
    
    # Process queries offline with original indices; sort by x descending
    newQueries = [(x, y, idx) for idx, (x, y) in enumerate(queries)]
    newQueries.sort(key=lambda x: x[0], reverse=True)
    
    # Coordinate compression for nums2 values
    all_nums2 = sorted(set(nums2))
    comp = {value: i+1 for i, value in enumerate(all_nums2)}  # mapping to 1-indexed BIT positions

    # Initialize BIT structure with size equal to the number of unique nums2 values.
    tree = FenwickTree(len(all_nums2))
    res = [0] * len(queries)
    pIdx = 0

    # Function to query BIT for indices corresponding to nums2 >= target value
    # Since BIT is constructed for prefix maximum queries, we simulate a query by iterating over valid indices.
    def query_range(bit, start_index, size):
        best = float('-inf')
        # Start at start_index and accumulate values using BIT properties:
        # A standard BIT does not support range queries in reverse. Given our constraints, we instead
        # iterate (logarithmically many steps) to combine the Fenwick tree nodes that cover [start_index, size].
        i = start_index
        while i <= size:
            best = max(best, bit.data[i])
            i += i & -i
        return best

    for x, y, qi in newQueries:
        # Add all points with nums1 >= current query x.
        while pIdx < n and points[pIdx][0] >= x:
            num1_val, num2_val, sum_val = points[pIdx]
            tree.update(comp[num2_val], sum_val)
            pIdx += 1
        # Find the smallest compressed index where original nums2 value is >= query y.
        import bisect
        pos = bisect.bisect_left(all_nums2, y) + 1  # convert to 1-indexed
        if pos > len(all_nums2):
            res[qi] = -1
        else:
            max_sum = query_range(tree, pos, len(all_nums2))
            res[qi] = max_sum if max_sum != float('-inf') else -1
    return res

# Example usage
nums1 = [4, 3, 1, 2]
nums2 = [2, 4, 9, 5]
queries = [[4, 1], [1, 3], [2, 5]]
print(maximumSumQueries(nums1, nums2, queries))  # Expected Output: [6, 10, 7]