LeetCode 2070 - Most Beautiful Item for Each Query

The problem gives us a list of items, where each item has two properties: - price - beauty Each entry looks like: We are also given a list of queries.

leetcodemediumarraybinary-searchsorting

LeetCode Problem 2070

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sorting

Solution

Problem Understanding

The problem gives us a list of items, where each item has two properties:

  • price
  • beauty

Each entry looks like:

items[i] = [pricei, beautyi]

We are also given a list of queries. For every query value queries[j], we must determine:

Among all items whose price is less than or equal to the query value, what is the maximum beauty?

If no item satisfies the price condition, the answer for that query is 0.

The result should be an array where each position corresponds to the answer for the matching query.

For example, suppose we have:

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

For query 2, we can choose items with prices 1 and 2, so the maximum beauty is 4.

For query 4, we still cannot use the item priced at 5, so the maximum beauty remains 4.

The constraints are extremely important:

  • Up to 10^5 items
  • Up to 10^5 queries
  • Prices and beauties can be as large as 10^9

These limits immediately tell us that a naive nested loop solution will be too slow. A solution with time complexity around O(n * q) could require up to 10^10 operations in the worst case, which is not feasible.

The problem also allows:

  • Multiple items with the same price
  • Multiple items with the same beauty
  • Queries smaller than every item price
  • Queries larger than every item price

These edge cases are important because they affect how we preprocess and search efficiently.

Approaches

Brute Force Approach

The most straightforward solution is to process each query independently.

For every query:

  1. Iterate through all items.
  2. Check whether price <= query.
  3. Track the maximum beauty among valid items.

This works because it directly implements the problem definition. Every eligible item is examined, so the maximum beauty found is guaranteed to be correct.

However, the performance is unacceptable for large inputs.

If there are:

  • n items
  • m queries

then we perform n * m comparisons.

With both values up to 10^5, this becomes too large.

Key Insight for the Optimal Solution

The important observation is that queries only care about:

The maximum beauty among all items with price up to some limit.

This suggests sorting.

If we sort items by price, then as prices increase, we can maintain a running maximum beauty.

For example:

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

After preprocessing:

Price Best Beauty So Far
1 2
2 4
3 5
5 6

Now each query becomes:

Find the rightmost item whose price is <= query.

That can be done efficiently using binary search.

Once we locate that position, the precomputed running maximum immediately gives the answer.

This transforms the problem from repeated scanning into:

  • One sorting step
  • One preprocessing pass
  • One binary search per query

This is efficient enough for the constraints.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(n × m) O(1) Scans every item for every query
Optimal O(n log n + m log n) O(n) Sort items and use binary search

Algorithm Walkthrough

Optimal Algorithm

  1. Sort all items by price.

This allows us to process items in increasing price order. Binary search also requires sorted data. 2. Build two arrays:

  • prices, containing sorted prices
  • max_beauty, where max_beauty[i] stores the maximum beauty seen from index 0 through i

For example:

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

After preprocessing:

prices = [1,2,3,5]
max_beauty = [2,4,4,6]

Notice that even though beauty at price 3 is only 2, the best beauty up to that point is still 4. 3. For each query, perform binary search on prices.

We want the rightmost index where:

prices[index] <= query

Python's bisect_right or Go's sort.Search can efficiently find this position. 4. If no valid index exists, return 0.

This happens when the query is smaller than the smallest item price. 5. Otherwise, return max_beauty[index].

Since max_beauty[index] already stores the best beauty among all valid prices, this is the correct answer.

Why it works

The correctness relies on a simple invariant:

After preprocessing, max_beauty[i] always equals the maximum beauty among all items with indices from 0 to i.

Because items are sorted by price, every index before i has a price less than or equal to prices[i].

Binary search finds the largest valid price position for the query. The prefix maximum array then instantly provides the best beauty among all eligible items.

Therefore, every query is answered correctly.

Python Solution

from bisect import bisect_right
from typing import List

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # Sort items by price
        items.sort()

        prices = []
        max_beauty = []

        current_max = 0

        # Build prefix maximum beauty array
        for price, beauty in items:
            current_max = max(current_max, beauty)

            prices.append(price)
            max_beauty.append(current_max)

        answers = []

        # Answer each query using binary search
        for query in queries:
            index = bisect_right(prices, query) - 1

            if index >= 0:
                answers.append(max_beauty[index])
            else:
                answers.append(0)

        return answers

The implementation begins by sorting items by price. Python automatically sorts pairs lexicographically, so sorting directly works correctly.

Next, the code builds two arrays:

  • prices
  • max_beauty

The variable current_max tracks the best beauty encountered so far while iterating through sorted items.

For every item:

current_max = max(current_max, beauty)

This ensures that max_beauty[i] stores the best beauty among all prices up to that point.

For queries, the solution uses:

bisect_right(prices, query)

This returns the insertion position after all values less than or equal to the query. Subtracting one gives the index of the largest valid price.

If the index becomes negative, no item is affordable, so the answer is 0.

Otherwise, the prefix maximum array provides the answer immediately.

Go Solution

package main

import "sort"

func maximumBeauty(items [][]int, queries []int) []int {
	sort.Slice(items, func(i, j int) bool {
		return items[i][0] < items[j][0]
	})

	prices := make([]int, len(items))
	maxBeauty := make([]int, len(items))

	currentMax := 0

	for i, item := range items {
		price := item[0]
		beauty := item[1]

		if beauty > currentMax {
			currentMax = beauty
		}

		prices[i] = price
		maxBeauty[i] = currentMax
	}

	result := make([]int, len(queries))

	for i, query := range queries {
		index := sort.Search(len(prices), func(j int) bool {
			return prices[j] > query
		}) - 1

		if index >= 0 {
			result[i] = maxBeauty[index]
		} else {
			result[i] = 0
		}
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python solution.

The main difference is binary search syntax. Go uses:

sort.Search

which returns the first position where the condition becomes true. We search for the first price greater than the query, then subtract one to obtain the last valid price.

Go slices are used instead of Python lists, but the preprocessing logic remains identical.

Integer overflow is not a concern because the problem constraints fit comfortably within Go's standard int type on LeetCode systems.

Worked Examples

Example 1

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

Step 1: Sort Items

[[1,2],[2,4],[3,2],[3,5],[5,6]]

Step 2: Build Prefix Maximums

Index Price Beauty Running Max Beauty
0 1 2 2
1 2 4 4
2 3 2 4
3 3 5 5
4 5 6 6

Resulting arrays:

prices = [1,2,3,3,5]
max_beauty = [2,4,4,5,6]

Step 3: Process Queries

Query Rightmost Valid Price Index Answer
1 0 2
2 1 4
3 3 5
4 3 5
5 4 6
6 4 6

Final output:

[2,4,5,5,6,6]

Example 2

items = [[1,2],[1,2],[1,3],[1,4]]
queries = [1]

Sorted Items

[[1,2],[1,2],[1,3],[1,4]]

Prefix Maximums

Index Price Beauty Running Max
0 1 2 2
1 1 2 2
2 1 3 3
3 1 4 4

Arrays:

prices = [1,1,1,1]
max_beauty = [2,2,3,4]

Query Processing

For query 1, binary search returns index 3.

Answer:

max_beauty[3] = 4

Final output:

[4]

Example 3

items = [[10,1000]]
queries = [5]

Sorted Items

[[10,1000]]

Query Processing

No price is less than or equal to 5.

Binary search returns:

index = -1

Therefore:

answer = 0

Final output:

[0]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n + m log n) Sorting costs O(n log n), each query uses binary search
Space O(n) Stores prices and prefix maximum arrays

The dominant cost comes from sorting the items. After preprocessing, each query is answered independently in logarithmic time using binary search. This is efficient enough for the input limit of 10^5.

Test Cases

from typing import List

class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        from bisect import bisect_right

        items.sort()

        prices = []
        max_beauty = []

        current_max = 0

        for price, beauty in items:
            current_max = max(current_max, beauty)

            prices.append(price)
            max_beauty.append(current_max)

        result = []

        for query in queries:
            index = bisect_right(prices, query) - 1

            if index >= 0:
                result.append(max_beauty[index])
            else:
                result.append(0)

        return result

sol = Solution()

assert sol.maximumBeauty(
    [[1,2],[3,2],[2,4],[5,6],[3,5]],
    [1,2,3,4,5,6]
) == [2,4,5,5,6,6]  # Provided example 1

assert sol.maximumBeauty(
    [[1,2],[1,2],[1,3],[1,4]],
    [1]
) == [4]  # Duplicate prices

assert sol.maximumBeauty(
    [[10,1000]],
    [5]
) == [0]  # No affordable item

assert sol.maximumBeauty(
    [[5,10]],
    [5]
) == [10]  # Single exact match

assert sol.maximumBeauty(
    [[1,1],[2,2],[3,3]],
    [0]
) == [0]  # Query smaller than all prices

assert sol.maximumBeauty(
    [[1,5],[2,3],[3,10]],
    [1,2,3]
) == [5,5,10]  # Prefix maximum needed

assert sol.maximumBeauty(
    [[3,4],[2,5],[1,2]],
    [2]
) == [5]  # Unsorted input

assert sol.maximumBeauty(
    [[1,100]],
    [1,2,3]
) == [100,100,100]  # Query larger than all prices

assert sol.maximumBeauty(
    [[1,2],[2,2],[3,2]],
    [1,2,3]
) == [2,2,2]  # Same beauty values

assert sol.maximumBeauty(
    [[1000000000,1000000000]],
    [1000000000]
) == [1000000000]  # Maximum constraint values

Test Case Summary

Test Why
Example 1 Validates standard mixed behavior
Example 2 Validates duplicate prices
Example 3 Validates no valid item case
Single exact match Ensures equality condition works
Query smaller than all prices Tests negative binary search result
Prefix maximum needed Ensures running maximum logic is correct
Unsorted input Confirms sorting works properly
Query larger than all prices Ensures rightmost selection works
Same beauty values Tests repeated beauty handling
Maximum constraint values Validates large integer handling

Edge Cases

Queries Smaller Than Every Item Price

If a query value is smaller than the minimum item price, then no item is affordable.

This is a common source of bugs because binary search may return position 0, and subtracting one produces -1.

The implementation explicitly checks:

if index >= 0

If not, it returns 0.

Multiple Items With the Same Price

The problem allows duplicate prices.

For example:

[[1,2],[1,5],[1,3]]

A naive implementation might accidentally stop at the first matching price instead of considering all items.

Using bisect_right ensures we locate the last occurrence of that price. The prefix maximum array then guarantees the best beauty is returned.

Beauty Values That Decrease

Items are not guaranteed to have increasing beauty.

For example:

[[1,10],[2,3],[3,5]]

If we only stored raw beauty values, queries for 2 would incorrectly return 3 instead of 10.

The prefix maximum preprocessing fixes this by ensuring:

max_beauty[i]

always stores the best beauty seen so far.

Large Input Sizes

With up to 10^5 items and queries, inefficient solutions quickly time out.

The optimized approach avoids repeated scanning by combining sorting and binary search. This keeps the runtime within acceptable limits even at maximum constraints.