Problem Description

You have a collection of items, where each item has two properties: a price and a beauty value. These items are given as a 2D array items where items[i] = [price_i, beauty_i].

You also have a list of queries represented as an array of integers. For each query value queries[j], you need to find the maximum beauty among all items whose price is less than or equal to that query value.

For example:

• If queries[j] = 10, you need to look at all items with price ≤ 10 and find the one with the highest beauty value
• If no items have a price ≤ queries[j], the answer for that query is 0

Your task is to return an array answer where answer[j] contains the maximum beauty value for the corresponding queries[j].

The solution uses a sorting and offline query approach:

1. First, it sorts the items by price in ascending order
2. It processes queries in sorted order (from smallest to largest query value)
3. For each query, it uses a pointer to iterate through items whose prices are within the query limit, keeping track of the maximum beauty seen so far
4. Since queries are processed in sorted order but need to maintain their original positions, the solution uses sorted(zip(queries, range(m))) to keep track of original indices
5. The answer for each query is placed in its original position in the result array

This approach is efficient because each item is examined at most once across all queries, and the sorting allows us to process items incrementally as query values increase.

Intuition

The key insight is recognizing that if we process queries in a naive way (checking all items for each query), we'd repeatedly examine the same items, leading to inefficiency.

Think about it this way: if we have queries for prices 5, 10, and 15, the items valid for price 5 are also valid for prices 10 and 15. So why check them multiple times?

This leads us to the idea of sorting both items and queries by price. Once sorted, we can process queries in ascending order and maintain a running maximum beauty value. As we move from a smaller query to a larger one, we only need to consider the additional items that become available (those with prices between the previous and current query values).

The crucial observation is that once an item becomes "available" for a query (its price is within the limit), it remains available for all subsequent larger queries. This means we can use a two-pointer technique: one pointer iterates through queries, and another pointer iterates through items, never going backward.

However, there's a catch - we need to return answers in the original query order, not the sorted order. This is why we use the zip(queries, range(m)) technique to pair each query with its original index. After sorting and processing, we can place each answer back in its correct position.

The beauty of this approach is that each item is examined exactly once across all queries, reducing the time complexity from O(n * m) for the naive approach to O(n log n + m log m) for sorting plus O(n + m) for processing.

Learn more about Binary Search and Sorting patterns.

Solution Approach

The implementation follows the sorting and offline query strategy outlined in the reference approach. Let's walk through the code step by step:

Step 1: Sort the items array

items.sort()

We sort items by price in ascending order. This allows us to process items in order of increasing price.

Step 2: Initialize variables

n, m = len(items), len(queries)
ans = [0] * len(queries)
i = mx = 0

• n and m store the lengths of items and queries arrays
• ans is initialized with zeros to store the final results
• i is a pointer for traversing the items array
• mx tracks the maximum beauty seen so far

Step 3: Process queries in sorted order while preserving original indices

for q, j in sorted(zip(queries, range(m))):

This is the clever part: zip(queries, range(m)) creates pairs of (query_value, original_index). When we sort these pairs, they're sorted by query value, but we retain the original index j to know where to place the answer.

Step 4: Update maximum beauty for current query

while i < n and items[i][0] <= q:
    mx = max(mx, items[i][1])
    i += 1

For each query q, we advance the pointer i through all items whose price is at most q. We update mx to track the maximum beauty among all items seen so far. The key insight is that pointer i never moves backward - once an item is processed, it's available for all subsequent larger queries.

Step 5: Record the answer in the correct position

ans[j] = mx

We place the current maximum beauty mx at position j (the original index of this query) in the answer array.

Step 6: Return the result

return ans

The algorithm efficiently processes all queries in O(n log n + m log m + n + m) time, where the sorting dominates the complexity. Each item is examined exactly once across all queries, making this much more efficient than the naive O(n * m) approach.

Example Walkthrough

Let's walk through a concrete example to illustrate how the solution works.

Given:

• items = [[1, 2], [3, 2], [2, 4], [5, 6], [3, 5]]
• queries = [1, 2, 3, 4, 5, 6]

Step 1: Sort items by price After sorting: items = [[1, 2], [2, 4], [3, 2], [3, 5], [5, 6]]

Now items are arranged by price: 1, 2, 3, 3, 5

Step 2: Pair queries with their original indices and sort

• Original queries with indices: [(1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5)]
• After sorting by query value: [(1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (6, 5)] (In this case, queries were already sorted, but normally they might not be)

Step 3: Process each query in sorted order

Initialize: i = 0, mx = 0, ans = [0, 0, 0, 0, 0, 0]

• Query (1, 0): Find max beauty for price ≤ 1

  • Check item [1, 2]: price 1 ≤ 1 ✓, update mx = max(0, 2) = 2, advance i to 1
  • Check item [2, 4]: price 2 > 1 ✗, stop
  • Store ans[0] = 2

• Query (2, 1): Find max beauty for price ≤ 2

  • Continue from i = 1 (don't restart!)
  • Check item [2, 4]: price 2 ≤ 2 ✓, update mx = max(2, 4) = 4, advance i to 2
  • Check item [3, 2]: price 3 > 2 ✗, stop
  • Store ans[1] = 4

• Query (3, 2): Find max beauty for price ≤ 3

  • Continue from i = 2
  • Check item [3, 2]: price 3 ≤ 3 ✓, update mx = max(4, 2) = 4, advance i to 3
  • Check item [3, 5]: price 3 ≤ 3 ✓, update mx = max(4, 5) = 5, advance i to 4
  • Check item [5, 6]: price 5 > 3 ✗, stop
  • Store ans[2] = 5

• Query (4, 3): Find max beauty for price ≤ 4

  • Continue from i = 4
  • Check item [5, 6]: price 5 > 4 ✗, stop immediately
  • Store ans[3] = 5 (mx remains 5 from previous queries)

• Query (5, 4): Find max beauty for price ≤ 5

  • Continue from i = 4
  • Check item [5, 6]: price 5 ≤ 5 ✓, update mx = max(5, 6) = 6, advance i to 5
  • No more items to check
  • Store ans[4] = 6

• Query (6, 5): Find max beauty for price ≤ 6

  • Continue from i = 5
  • No more items to check (i >= n)
  • Store ans[5] = 6 (mx remains 6)

Final Result: ans = [2, 4, 5, 5, 6, 6]

The key efficiency comes from the fact that we never reset the pointer i - we process each item exactly once across all queries. The running maximum mx accumulates the best beauty value as we go, ensuring that larger queries automatically inherit the maximum beauty from all previously processed items.

Solution Implementation

Time and Space Complexity

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

The time complexity breaks down as follows:

• items.sort() takes O(n × log n) where n is the length of the items array
• sorted(zip(queries, range(m))) takes O(m × log m) where m is the length of the queries array
• The while loop inside the for loop processes each item at most once across all iterations, contributing O(n) in total
• The for loop iterates m times
• Overall: O(n × log n) + O(m × log m) + O(n + m) = O(n × log n + m × log m)

Space Complexity: O(log n + m)

The space complexity consists of:

• O(log n) for the sorting algorithm's recursive stack space when sorting items
• O(m) for the ans array which stores the results
• O(m) for the sorted queries with indices (created by sorted(zip(...)))
• O(log m) for the sorting algorithm's recursive stack space when sorting queries
• Overall: O(log n) + O(m) + O(log m) = O(log n + m) (since m dominates log m)

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

Common Pitfalls

Pitfall 1: Not Handling the Offline Query Indexing Correctly

A common mistake is forgetting to maintain the original query indices when sorting queries for processing. Developers might write:

# WRONG: This loses track of original positions
queries.sort()
for q in queries:
    # Process query q
    ans.append(max_beauty)  # Where does this go in the result?

Why it's wrong: After sorting queries, we lose the mapping between each query and its original position in the input array. The problem requires answers to be in the same order as the original queries.

Solution: Use sorted(zip(queries, range(num_queries))) to create pairs that maintain the original index alongside each query value. This allows processing queries in sorted order while knowing where to place each answer.

Pitfall 2: Resetting the Item Pointer for Each Query

Another mistake is resetting the item pointer for each new query:

# WRONG: Inefficient approach
for query_value, original_index in sorted(zip(queries, range(num_queries))):
    item_index = 0  # WRONG: Resetting pointer
    max_beauty = 0  # WRONG: Resetting max beauty
    while item_index < num_items and items[item_index][0] <= query_value:
        max_beauty = max(max_beauty, items[item_index][1])
        item_index += 1
    result[original_index] = max_beauty

Why it's wrong: This defeats the purpose of the offline query optimization. Since queries are processed in ascending order, items valid for a smaller query remain valid for larger queries. Resetting the pointer causes us to re-examine the same items multiple times, degrading performance to O(n * m).

Solution: Keep the item pointer (item_index) and max_beauty variables outside the query loop. Never reset them. This ensures each item is examined exactly once across all queries.

Pitfall 3: Not Considering Items with Same Price but Different Beauty Values

Some might incorrectly assume that when sorting items, they only need to keep the item with maximum beauty for each price:

# WRONG: Losing information during preprocessing
price_to_beauty = {}
for price, beauty in items:
    price_to_beauty[price] = max(price_to_beauty.get(price, 0), beauty)
items = [[p, b] for p, b in price_to_beauty.items()]

Why it's wrong: While this might seem like an optimization, it's unnecessary and complicates the code. The original algorithm handles duplicate prices correctly by considering all items and tracking the maximum beauty incrementally.

Solution: Simply sort the items as they are. The algorithm naturally handles multiple items with the same price by updating max_beauty as it encounters each one.