LeetCode Problem 2736

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Stack, Binary Indexed Tree, Segment Tree, Sorting, Monotonic Stack

Solution

LeetCode 2736 - Maximum Sum Queries

Problem Understanding

We are given two arrays, nums1 and nums2, both of length n. Each index j represents a point:

$$(nums1[j], nums2[j])$$

and has an associated value:

$$nums1[j] + nums2[j]$$

For every query [xi, yi], we must find an index j such that:

$$nums1[j] \ge xi$$

and

$$nums2[j] \ge yi$$

Among all indices satisfying both constraints, we want the maximum possible value:

$$nums1[j] + nums2[j]$$

If no index satisfies both requirements, the answer for that query is -1.

In other words, each query defines a rectangle in the coordinate plane:

$$[x_i,\infty) \times [y_i,\infty)$$

We must find the point lying inside that rectangle whose value nums1 + nums2 is largest.

The constraints are very large:

• n ≤ 100,000
• queries.length ≤ 100,000
• Values can be as large as 10^9

These constraints immediately rule out any solution that examines every array element for every query.

Important edge cases include:

• No valid point satisfies a query.
• Multiple points satisfy a query, requiring the maximum sum.
• Duplicate coordinates.
• Queries with extremely large thresholds.
• Queries that accept almost every point.

The challenge is answering up to 100,000 rectangle queries efficiently.

Approaches

Brute Force

For every query, iterate through all indices j.

For each index:

• Check whether nums1[j] >= xi
• Check whether nums2[j] >= yi
• If both hold, update the maximum value of nums1[j] + nums2[j]

This produces the correct answer because it explicitly checks every candidate.

However, its complexity is:

$$O(n \times q)$$

With both n and q potentially equal to 100,000, this becomes:

$$10^{10}$$

operations, which is far beyond practical limits.

Key Insight

Observe that queries only require points whose:

$$nums1 \ge xi$$

If we process queries in decreasing order of xi, we can gradually add points whose nums1 value is large enough.

Suppose points are sorted by descending nums1.

When processing a query with threshold xi:

• Every point with nums1 >= xi should already be available.
• Every point with nums1 < xi should not yet be added.

Now the problem becomes:

Given a set of active points, find among those with

$$nums2 \ge yi$$

the maximum value of

$$nums1 + nums2$$

This becomes a one-dimensional query on nums2.

The difficult part is supporting:

• insertion of points
• querying maximum sum for all nums2 >= yi

efficiently.

The official optimal solution uses a monotonic structure maintained over nums2 values. Each active point contributes:

• coordinate: nums2
• value: nums1 + nums2

The structure keeps only non-dominated points and allows binary search over nums2.

This yields an overall complexity of:

$$O((n+q)\log n)$$

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(nq)	O(1)	Check every index for every query
Optimal	O((n+q) log n)	O(n)	Offline processing with sorting, monotonic stack, and binary search

Algorithm Walkthrough

Optimal Offline Algorithm

We create triples:

$$(nums1[i], nums2[i], nums1[i]+nums2[i])$$

for every index.

We sort these points by decreasing nums1.

We also augment each query with its original index and sort all queries by decreasing xi.

We maintain:

• pointer p into the sorted points
• a monotonic structure stack

Each entry in stack stores:

(nums2, bestSum)

where:

• nums2 values are strictly increasing
• bestSum values are strictly decreasing

This structure contains only non-dominated candidates.

Step-by-Step

1. Sort all points by decreasing nums1.
2. Sort all queries by decreasing xi.
3. Initialize an empty monotonic stack.
4. Process queries in sorted order.
5. For the current query (xi, yi), add every point whose nums1 >= xi.
6. When inserting a point (y, value):

• If an existing point has both:

• larger or equal y

• larger or equal value

then the new point is useless.

• Similarly, while the new point dominates points at the end of the stack, remove those dominated points.

7. Insert the new point into the stack.
8. After all eligible points are inserted, binary search the stack for the first entry whose nums2 >= yi.
9. If such an entry exists, its stored value is the answer.
10. Otherwise return -1.
11. Store the result at the query's original index.
12. Continue until every query has been processed.

Why it Works

At any moment, the active set contains exactly the points satisfying the current nums1 threshold because queries are processed in decreasing xi.

The monotonic structure removes every dominated point. A point is dominated if another point has both a larger nums2 coordinate and a larger sum value. Such a point can never be optimal for any future query.

Therefore the stack contains precisely the Pareto-optimal candidates. Because nums2 values are sorted and sums are monotonic, binary search finds the best valid point for any yi threshold. Thus every query receives the correct maximum sum.

Python Solution

from typing import List
from bisect import bisect_left

class Solution:
    def maximumSumQueries(
        self,
        nums1: List[int],
        nums2: List[int],
        queries: List[List[int]]
    ) -> List[int]:

        n = len(nums1)

        points = sorted(
            zip(nums1, nums2),
            reverse=True
        )

        indexed_queries = sorted(
            [(x, y, i) for i, (x, y) in enumerate(queries)],
            reverse=True
        )

        answer = [-1] * len(queries)

        stack = []
        ptr = 0

        for x, y, query_index in indexed_queries:

            while ptr < n and points[ptr][0] >= x:

                px, py = points[ptr]
                current_sum = px + py

                while stack and stack[-1][1] <= current_sum:
                    stack.pop()

                if not stack or stack[-1][0] < py:
                    stack.append((py, current_sum))

                ptr += 1

            left = 0
            right = len(stack)

            while left < right:
                mid = (left + right) // 2

                if stack[mid][0] >= y:
                    right = mid
                else:
                    left = mid + 1

            if left < len(stack):
                answer[query_index] = stack[left][1]

        return answer

Implementation Explanation

The points are sorted by descending nums1, allowing us to activate points as query thresholds decrease.

Queries are also sorted by descending xi. When processing a query, every point satisfying nums1 >= xi is inserted exactly once.

Each inserted point contributes:

current_sum = nums1 + nums2

The stack maintains only useful candidates. Any candidate with a smaller or equal sum than a newly inserted candidate becomes irrelevant and is removed.

The remaining entries have increasing nums2 values and decreasing sums, which permits binary searching for the first valid nums2 >= yi.

The answer is written back to the original query position using the stored query index.

Go Solution

package main

import "sort"

func maximumSumQueries(nums1 []int, nums2 []int, queries [][]int) []int {
	type Point struct {
		x int
		y int
	}

	type Query struct {
		x   int
		y   int
		idx int
	}

	n := len(nums1)

	points := make([]Point, n)
	for i := 0; i < n; i++ {
		points[i] = Point{nums1[i], nums2[i]}
	}

	sort.Slice(points, func(i, j int) bool {
		return points[i].x > points[j].x
	})

	qs := make([]Query, len(queries))
	for i, q := range queries {
		qs[i] = Query{q[0], q[1], i}
	}

	sort.Slice(qs, func(i, j int) bool {
		return qs[i].x > qs[j].x
	})

	answer := make([]int, len(queries))
	for i := range answer {
		answer[i] = -1
	}

	type Pair struct {
		y   int
		sum int
	}

	stack := make([]Pair, 0)
	ptr := 0

	for _, q := range qs {

		for ptr < n && points[ptr].x >= q.x {

			sum := points[ptr].x + points[ptr].y

			for len(stack) > 0 &&
				stack[len(stack)-1].sum <= sum {
				stack = stack[:len(stack)-1]
			}

			if len(stack) == 0 ||
				stack[len(stack)-1].y < points[ptr].y {
				stack = append(stack, Pair{
					y:   points[ptr].y,
					sum: sum,
				})
			}

			ptr++
		}

		pos := sort.Search(len(stack), func(i int) bool {
			return stack[i].y >= q.y
		})

		if pos < len(stack) {
			answer[q.idx] = stack[pos].sum
		}
	}

	return answer
}

Go-Specific Notes

The algorithm is identical to the Python version.

Go uses sort.Slice for sorting and sort.Search for binary search. Integer overflow is not a concern because:

$$nums1[i] + nums2[i] \le 2 \times 10^9$$

which fits comfortably within Go's int on LeetCode's 64-bit environment.

Slices are used to implement the monotonic stack efficiently.

Worked Examples

Example 1

Input:

nums1 = [4,3,1,2]
nums2 = [2,4,9,5]
queries = [[4,1],[1,3],[2,5]]

Points sorted by nums1:

nums1	nums2	sum
4	2	6
3	4	7
2	5	7
1	9	10

Queries sorted by xi:

xi	yi
4	1
2	5
1	3

Processing (4,1):

Stack
(2,6)

Binary search for y >= 1 gives 6.

Processing (2,5):

Add (4,7) then (5,7).

Stack becomes:

y	sum
5	7

Binary search for y >= 5 gives 7.

Processing (1,3):

Add (9,10).

Stack becomes:

y	sum
9	10

Binary search for y >= 3 gives 10.

Final answers:

[6,10,7]

Example 2

Input:

nums1 = [3,2,5]
nums2 = [2,3,4]

Sorted points:

nums1	nums2	sum
5	4	9
3	2	5
2	3	5

The point (5,4) dominates all others.

For every query, binary search finds sum 9.

Result:

[9,9,9]

Example 3

Input:

nums1 = [2,1]
nums2 = [2,3]
queries = [[3,3]]

No point satisfies:

nums1 >= 3

No points are inserted.

Stack remains empty.

Answer:

[-1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O((n + q) log n)	Sorting plus binary searches
Space	O(n)	Monotonic stack and auxiliary arrays

The sorting phase costs:

$$O(n \log n + q \log q)$$

Each point is inserted once and removed at most once from the stack, giving linear stack maintenance.

Each query performs one binary search, contributing:

$$O(q \log n)$$

Combining everything yields:

$$O((n+q)\log n)$$

time and O(n) auxiliary space.

Test Cases

sol = Solution()

# Example 1
assert sol.maximumSumQueries(
    [4,3,1,2],
    [2,4,9,5],
    [[4,1],[1,3],[2,5]]
) == [6,10,7]

# Example 2
assert sol.maximumSumQueries(
    [3,2,5],
    [2,3,4],
    [[4,4],[3,2],[1,1]]
) == [9,9,9]

# Example 3
assert sol.maximumSumQueries(
    [2,1],
    [2,3],
    [[3,3]]
) == [-1]

# Single element valid
assert sol.maximumSumQueries(
    [5],
    [7],
    [[1,1]]
) == [12]

# Single element invalid
assert sol.maximumSumQueries(
    [5],
    [7],
    [[6,1]]
) == [-1]

# Duplicate points
assert sol.maximumSumQueries(
    [3,3,3],
    [4,4,4],
    [[3,4]]
) == [7]

# Query exactly matching point
assert sol.maximumSumQueries(
    [2,5,8],
    [1,4,7],
    [[5,4]]
) == [15]

# Large threshold excludes all
assert sol.maximumSumQueries(
    [1,2,3],
    [1,2,3],
    [[100,100]]
) == [-1]

# Multiple candidates, choose maximum sum
assert sol.maximumSumQueries(
    [5,6,7],
    [10,2,8],
    [[5,2]]
) == [15]

# Many queries
assert sol.maximumSumQueries(
    [1,2,3],
    [3,2,1],
    [[1,1],[2,2],[3,3]]
) == [4,4,-1]

Test Summary

Test	Why
Example 1	Official mixed example
Example 2	One point dominates all
Example 3	No valid answer
Single element valid	Smallest valid input
Single element invalid	Smallest invalid input
Duplicate points	Handles repeated coordinates
Exact threshold match	Boundary condition
Large threshold excludes all	Empty active set
Multiple candidates	Must choose maximum sum
Many queries	Different thresholds in one run

Edge Cases

No Valid Point Exists

A query may require values larger than every point in the dataset. In this situation no point is activated or no activated point satisfies the nums2 threshold. The binary search fails to find a candidate, and the answer remains -1.

Multiple Valid Points With Different Sums

Many points may satisfy both constraints. Returning the first matching point would be incorrect. The monotonic structure stores only the best non-dominated candidates, guaranteeing that the returned value is the maximum possible sum.

Duplicate Coordinates

Several indices may share identical (nums1, nums2) values. A careless implementation could keep redundant entries and increase memory usage. The monotonic stack removes dominated candidates, naturally handling duplicates without affecting correctness.

Exact Threshold Boundaries

The problem uses >=, not >. Queries where xi or yi exactly equal a point's coordinates must include that point. The algorithm activates points with nums1 >= xi and binary searches for the first nums2 >= yi, preserving the required inclusive behavior.

Extremely Large Values

Values may reach 10^9, making coordinate compression based on dense arrays impossible. The offline sorting and monotonic-stack approach works directly on the original values and therefore scales correctly to the full constraint range.