Problem Description

You have two arrays nums1 and nums2, both containing integers and having the same length n. The arrays are 0-indexed.

You're also given a list of queries, where each query queries[i] contains two values: [xi, yi].

For each query, you need to find the maximum possible sum nums1[j] + nums2[j] where:

• The index j must satisfy: 0 <= j < n
• nums1[j] must be greater than or equal to xi
• nums2[j] must be greater than or equal to yi

If no valid index j exists that satisfies both conditions, the answer for that query is -1.

Your task is to return an array where each element corresponds to the answer for each query in order.

Example:

If nums1 = [4, 3, 1, 2] and nums2 = [2, 4, 9, 5], and you have a query [x=3, y=4]:

• Index 0: nums1[0]=4 >= 3 and nums2[0]=2 < 4 - doesn't satisfy both conditions
• Index 1: nums1[1]=3 >= 3 and nums2[1]=4 >= 4 - satisfies both conditions, sum = 3+4 = 7
• Index 2: nums1[2]=1 < 3 - doesn't satisfy the first condition
• Index 3: nums1[3]=2 < 3 - doesn't satisfy the first condition

The maximum valid sum would be 7 from index 1.

Intuition

The naive approach would be to check every index for every query, but this would be inefficient with time complexity O(m * n) where m is the number of queries and n is the array length.

The key insight is recognizing this as a two-dimensional constraint problem: for each query, we need indices where both nums1[j] >= x AND nums2[j] >= y. When dealing with two dimensions, we can often optimize by sorting one dimension and using a data structure to efficiently handle the other.

Let's think about how sorting helps. If we sort queries by their x values in descending order, we can process them from largest to smallest x. As we move to queries with smaller x values, more indices from nums1 become valid (since the constraint nums1[j] >= x becomes easier to satisfy). This means we can incrementally add valid indices as we process queries.

Similarly, if we sort the pairs (nums1[i], nums2[i]) by nums1 values in descending order, we can efficiently find all indices where nums1[j] >= x by maintaining a pointer that moves forward as we process queries with decreasing x values.

Now the challenge becomes: among all indices where nums1[j] >= x, how do we quickly find the maximum nums1[j] + nums2[j] where nums2[j] >= y?

This is where the Binary Indexed Tree (Fenwick Tree) comes in. As we process queries and add valid indices based on the nums1 constraint, we can insert these values into a BIT organized by nums2 values. The BIT allows us to efficiently query for the maximum sum among all entries where nums2[j] >= y.

The trick is to discretize the nums2 values (map them to ranks) so we can use them as indices in the BIT. By storing the maximum nums1[j] + nums2[j] at each position, we can query for the maximum sum in the range where nums2[j] >= y in O(log n) time.

This approach reduces the overall complexity from O(m * n) to O((n + m) * log n + m * log m), making it much more efficient for large inputs.

Learn more about Stack, Segment Tree, Binary Search, Sorting and Monotonic Stack patterns.

Solution Approach

The solution implements a Binary Indexed Tree (BIT) to efficiently handle the two-dimensional partial order problem. Let's walk through the implementation step by step:

1. Binary Indexed Tree Implementation:

The BinaryIndexedTree class maintains an array c where c[x] stores the maximum value for a range. The tree supports:

• update(x, v): Updates position x with value v if v is greater than the current maximum
• query(x): Returns the maximum value in the range [1, x]

The BIT uses the property that x & -x gives the rightmost set bit, allowing efficient range updates and queries in O(log n) time.

2. Main Algorithm:

nums = sorted(zip(nums1, nums2), key=lambda x: -x[0])

First, we create pairs of (nums1[i], nums2[i]) and sort them in descending order by the first element. This allows us to process elements with larger nums1 values first.

nums2.sort()

We sort nums2 separately to enable binary search for discretization. This sorted array helps us map nums2 values to indices for the BIT.

for i in sorted(range(m), key=lambda i: -queries[i][0]):

We process queries in descending order of their x values. This ensures that as we move to smaller x values, we can incrementally add more valid elements.

3. Processing Each Query:

For each query (x, y):

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

• We add all pairs where nums1 >= x to the BIT
• bisect_left(nums2, nums[j][1]) finds the position of nums[j][1] in the sorted nums2
• We use k = n - bisect_left(...) to reverse the index (storing larger values at smaller indices in BIT)
• We update the BIT at position k with the sum nums[j][0] + nums[j][1]

k = n - bisect_left(nums2, y)
ans[i] = tree.query(k)

• We find the discretized position for y
• Query the BIT for the maximum sum where nums2 >= y
• Store the result in the appropriate position of the answer array

4. Why This Works:

The algorithm maintains the invariant that when processing query i, the BIT contains all pairs where nums1 >= queries[i][0]. By organizing the BIT by nums2 values (in reverse order), querying position k gives us the maximum sum among all pairs where both constraints are satisfied.

The reverse indexing (n - bisect_left(...)) is crucial because BIT naturally handles prefix maximum queries. By reversing the indices, a prefix query on the BIT becomes a suffix query on the original nums2 values, which corresponds to finding values >= y.

Time Complexity: O((n + m) × log n + m × log m)

• Sorting: O(n log n + m log m)
• Processing queries: O(m log n) for binary searches
• BIT operations: O(n log n) for updates and O(m log n) for queries

Space Complexity: O(n + m) for the BIT and result array

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Given:

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

Step 1: Prepare the data

First, create pairs and sort them by nums1 descending:

• Original pairs: [(4,2), (3,4), (1,9), (2,5)]
• Sorted pairs: [(4,2), (3,4), (2,5), (1,9)]

Sort nums2 for discretization: [2, 4, 5, 9]

Sort query indices by x-value descending:

• Query 0: [3, 4] (x=3)
• Query 1: [1, 8] (x=1)
• Query 2: [5, 1] (x=5)
• Processing order: Query 2 → Query 0 → Query 1

Step 2: Process Query 2 [x=5, y=1]

Initialize: j = 0, BIT is empty

Check pairs where nums1 >= 5:

• Pair (4,2): 4 < 5 ❌ - stop here

No valid pairs added to BIT.

Query BIT for y=1:

• Find position: k = 4 - bisect_left([2,4,5,9], 1) = 4 - 0 = 4
• BIT.query(4) returns -1 (no valid pairs)

Result: ans[2] = -1

Step 3: Process Query 0 [x=3, y=4]

Current: j = 0, BIT is empty

Add pairs where nums1 >= 3:

• Pair (4,2): 4 >= 3 ✓
  • Find position: k = 4 - bisect_left([2,4,5,9], 2) = 4 - 0 = 4
  • BIT.update(4, 4+2=6)
• Pair (3,4): 3 >= 3 ✓
  • Find position: k = 4 - bisect_left([2,4,5,9], 4) = 4 - 1 = 3
  • BIT.update(3, 3+4=7)
• Pair (2,5): 2 < 3 ❌ - stop here

Now j = 2, BIT contains: {position 4: sum=6, position 3: sum=7}

Query BIT for y=4:

• Find position: k = 4 - bisect_left([2,4,5,9], 4) = 4 - 1 = 3
• BIT.query(3) returns max(values at positions 1-3) = 7

Result: ans[0] = 7

Step 4: Process Query 1 [x=1, y=8]

Current: j = 2, BIT has pairs (4,2) and (3,4)

Add pairs where nums1 >= 1:

• Pair (2,5): 2 >= 1 ✓
  • Find position: k = 4 - bisect_left([2,4,5,9], 5) = 4 - 2 = 2
  • BIT.update(2, 2+5=7)
• Pair (1,9): 1 >= 1 ✓
  • Find position: k = 4 - bisect_left([2,4,5,9], 9) = 4 - 3 = 1
  • BIT.update(1, 1+9=10)

Now j = 4, BIT contains all pairs

Query BIT for y=8:

• Find position: k = 4 - bisect_left([2,4,5,9], 8) = 4 - 3 = 1
• BIT.query(1) returns max(values at position 1) = 10

Result: ans[1] = 10

Final Answer: [7, 10, -1]

The key insight is that by processing queries in descending order of x-values, we incrementally add valid pairs to the BIT. The BIT, organized by discretized nums2 values in reverse order, allows us to efficiently find the maximum sum among pairs satisfying both constraints.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n log n + m log m + (n + m) log n)

Breaking down the operations:

• Sorting nums by first element: O(n log n)
• Sorting nums2: O(n log n)
• Sorting query indices: O(m log m)
• Processing each query:
  • For each of m queries, we potentially process some elements from nums (total across all queries is at most n)
  • For each element processed: binary search in nums2 takes O(log n) and BIT update takes O(log n)
  • For each query: binary search in nums2 takes O(log n) and BIT query takes O(log n)
• Total for query processing: O((n + m) log n)

Overall: O(n log n + m log m + (n + m) log n) which simplifies to O((n + m) log n + m log m)

Space Complexity: O(n + m)

Breaking down the space usage:

• BinaryIndexedTree array c: O(n)
• Sorted nums array (zip of nums1 and nums2): O(n)
• Answer array: O(m)
• Sorting operations use O(n) and O(m) auxiliary space for the respective arrays

The dominant space usage is O(n + m)

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Index Mapping for Binary Indexed Tree

One of the most common pitfalls in this solution is misunderstanding the index transformation when using the Binary Indexed Tree. The BIT is 1-indexed, but the position calculation uses 0-indexed arrays.

The Pitfall:

# Incorrect: forgetting that BIT is 1-indexed
position = n - bisect_left(nums2, pairs[pair_index][1])
fenwick_tree.update(position, sum_value)  # This could pass 0 to BIT!

When bisect_left(nums2, pairs[pair_index][1]) returns n (meaning the value is greater than or equal to all elements), the position becomes 0, which is invalid for a 1-indexed BIT.

The Solution:

# Correct: ensure position is always >= 1
position = n - bisect_left(nums2, pairs[pair_index][1])
# Add 1 to make it 1-indexed, but this changes the logic
# OR handle edge cases explicitly:
if position == 0:
    position = 1  # Map to index 1 for the largest values
fenwick_tree.update(position, sum_value)

2. Confusion with Coordinate Compression Direction

The solution uses reverse indexing (n - bisect_left(...)) to transform the problem, which can be counterintuitive.

The Pitfall:

# Incorrect: using forward indexing
position = bisect_left(nums2, pairs[pair_index][1]) + 1
fenwick_tree.update(position, sum_value)
# This would store smaller nums2 values at smaller indices
# Making prefix queries return max for nums2 <= y, not nums2 >= y!

Why Reverse Indexing Works:

• BIT naturally handles prefix maximum queries (indices 1 to k)
• By reversing indices, larger nums2 values get smaller indices
• A prefix query up to position k then captures all values where nums2 >= y

3. Not Handling Duplicate Values in nums2

When multiple elements in nums2 have the same value, bisect_left always returns the leftmost position, which could lead to incorrect index mapping.

The Pitfall:

nums2 = [1, 2, 2, 3]
# bisect_left(nums2, 2) always returns 1
# Multiple different pairs with nums2=2 map to the same BIT position

The Solution: The current implementation actually handles this correctly because:

• All pairs with the same nums2 value map to the same BIT position
• BIT's update operation keeps the maximum value at each position
• This naturally handles duplicates by storing the best sum for each nums2 value

4. Processing Order Dependencies

The algorithm relies on processing both pairs and queries in specific orders. Mixing up these orders breaks the algorithm.

The Pitfall:

# Incorrect: processing queries in arbitrary order
for query_index in range(m):  # Wrong! Must be sorted by queries[i][0]
    query_x, query_y = queries[query_index]
    # ...

Why Order Matters:

• Queries must be processed in descending order of x values
• This ensures we can incrementally add pairs to the BIT
• Each query sees all pairs with nums1 >= x that have been processed

5. Off-by-One Errors in Binary Search

Using the wrong binary search variant can cause subtle bugs.

The Pitfall:

# Using bisect_right instead of bisect_left
position = n - bisect_right(nums2, query_y)  # Wrong!

The Difference:

• bisect_left(nums2, y): finds the leftmost position where y could be inserted
• bisect_right(nums2, y): finds the rightmost position where y could be inserted
• For finding values >= y, we need bisect_left to include equal values

Example to Illustrate:

nums2_sorted = [1, 2, 3, 4]
y = 2
# bisect_left(nums2_sorted, 2) = 1  → n - 1 includes values >= 2
# bisect_right(nums2_sorted, 2) = 2 → n - 2 only includes values > 2