Most Beautiful Item for Each Query

Medium

Google

8 views

Topics:

ArraysBinary Search

You are given a 2D integer array items where items[i] = [price_i, beauty_i] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the j^th query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

Constraints:

1 <= items.length, queries.length <= 10⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

Try coding it in LeetCode

Most Beautiful Item for Each Query

Medium

Google

8 views

Topics:

ArraysBinary Search

You are given a 2D integer array items where items[i] = [price_i, beauty_i] denotes the price and beauty of an item respectively.

You are also given a 0-indexed integer array queries. For each queries[j], you want to determine the maximum beauty of an item whose price is less than or equal to queries[j]. If no such item exists, then the answer to this query is 0.

Return an array answer of the same length as queries where answer[j] is the answer to the j^th query.

Example 1:

Input: items = [[1,2],[3,2],[2,4],[5,6],[3,5]], queries = [1,2,3,4,5,6]
Output: [2,4,5,5,6,6]
Explanation:
- For queries[0]=1, [1,2] is the only item which has price <= 1. Hence, the answer for this query is 2.
- For queries[1]=2, the items which can be considered are [1,2] and [2,4]. 
  The maximum beauty among them is 4.
- For queries[2]=3 and queries[3]=4, the items which can be considered are [1,2], [3,2], [2,4], and [3,5].
  The maximum beauty among them is 5.
- For queries[4]=5 and queries[5]=6, all items can be considered.
  Hence, the answer for them is the maximum beauty of all items, i.e., 6.

Example 2:

Input: items = [[1,2],[1,2],[1,3],[1,4]], queries = [1]
Output: [4]
Explanation: 
The price of every item is equal to 1, so we choose the item with the maximum beauty 4. 
Note that multiple items can have the same price and/or beauty.

Example 3:

Input: items = [[10,1000]], queries = [5]
Output: [0]
Explanation:
No item has a price less than or equal to 5, so no item can be chosen.
Hence, the answer to the query is 0.

Constraints:

1 <= items.length, queries.length <= 10⁵
items[i].length == 2
1 <= price_i, beauty_i, queries[j] <= 10⁹

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the possible ranges for the beauty and price values within the items array and the price values within the queries array?
Can the items array be empty, and if so, what should the expected output be for an empty items array?
If multiple items have the same price and the maximum beauty for that price, which one should I consider the 'most beautiful'?
If a given query price is lower than the price of all items, should I return 0 for the beauty?
Is the items array sorted by price, or should I assume it is unsorted?

Brute Force Solution

Approach

The brute force approach means we will go through each question individually. For each question, we will examine every item to see if it meets the question's requirement and choose the 'most beautiful' one among those.

Here's how the algorithm would work step-by-step:

Take the first question from the list of questions.
Look at the first item in the collection of items.
Check if the item's price is less than or equal to the question's maximum price.
If the item's price is within the limit, remember its beauty value.
If the item's price is too high, ignore this item.
Repeat steps 2 through 5 for every item in the collection.
After checking all items, find the item with the highest beauty value among the ones that met the price requirement.
The beauty value of this most beautiful item is the answer to the question.
Repeat steps 1 through 8 for each question in the list of questions.

Code Implementation

def most_beautiful_item_for_each_query_brute_force(items, queries):
    results = []
    for maximum_price in queries:
        most_beautiful_value = 0
        # Iterate through each item to find the most beautiful within price limit

        for item in items:
            item_price = item[0]
            item_beauty = item[1]

            # Check if the current item's price is within the query's price limit
            if item_price <= maximum_price:

                #If it is within the limit, check if it is more beautiful than current most beautiful item
                if item_beauty > most_beautiful_value:
                    most_beautiful_value = item_beauty

        results.append(most_beautiful_value)

    return results

Big(O) Analysis

Time Complexity

O(m*n) – The algorithm iterates through each of the 'm' queries. For each query, it iterates through all 'n' items to find the most beautiful item within the price constraint. Therefore, the number of operations is directly proportional to the product of the number of queries and the number of items. This results in a time complexity of O(m*n), where 'm' is the number of queries and 'n' is the number of items.

Space Complexity

O(1) – The brute force approach iterates through the items and questions without using any auxiliary data structures that scale with the input size. It only uses a few variables to keep track of the current item's price and beauty, and the maximum beauty found so far for each question. The number of variables used does not depend on the number of items or questions, hence the space complexity is constant. Therefore, the auxiliary space complexity is O(1).

Optimal Solution

Approach

The optimal solution sorts the items by price, then builds a prefix maximum for the beauty values. Using binary search for each query enables us to efficiently locate the most beautiful item without exhaustively checking every item.

Here's how the algorithm would work step-by-step:

First, organize the items by their price, from cheapest to most expensive.
Then, create a record that, for each item, stores the maximum beauty seen so far, considering all items up to that price point. This 'maximum beauty so far' is updated as we go through the list.
For each price we're asked about in the query, use a fast search method to find the most expensive item that costs no more than that price. Since the list is sorted by price, a binary search is perfect.
Once we've found that item, we can simply look up its 'maximum beauty so far' value from the record we created earlier. This is the answer: the most beautiful item available for that price.

Code Implementation

def most_beautiful_item_for_each_query(items, queries):
    items.sort()
    max_beauty_so_far = 0
    prefix_max_beauty = []
    for price, beauty in items:
        max_beauty_so_far = max(max_beauty_so_far, beauty)
        prefix_max_beauty.append(max_beauty_so_far)

    result = []
    for query_price in queries:
        # Use binary search to find the most expensive item affordable.
        left_index = 0
        right_index = len(items) - 1
        most_expensive_index = -1

        while left_index <= right_index:
            middle_index = (left_index + right_index) // 2
            if items[middle_index][0] <= query_price:
                most_expensive_index = middle_index
                left_index = middle_index + 1
            else:
                right_index = middle_index - 1

        # If no affordable item, beauty is 0.
        if most_expensive_index == -1:
            result.append(0)
        else:
            # Get max beauty for affordable items
            result.append(prefix_max_beauty[most_expensive_index])

    return result

Big(O) Analysis

Time Complexity

O(n log n + q log n) – The solution first sorts the items, which takes O(n log n) time, where n is the number of items. Then, it iterates through the sorted items once to compute the prefix maximum of beauty values, which takes O(n) time. Finally, for each of the q queries, a binary search is performed on the sorted items, taking O(log n) time per query. Therefore, the total time complexity is O(n log n + n + q log n). Since n log n dominates n, we can simplify it to O(n log n + q log n).

Space Complexity

O(N) – The algorithm creates a sorted list of items, which in the worst-case scenario will be the same size as the input list of items, N. It also creates a 'maximum beauty so far' record that has one entry for each item in the sorted list, so it is also of size N. Therefore, the auxiliary space used is proportional to the number of items, N.

Edge Cases

Case	How to Handle
Empty items array	Return an empty list since no items exist.
Empty queries array	Return an empty list since there are no queries to process.
Items array with a single item	Return the beauty of the single item if its price is less than or equal to query or 0 otherwise.
All prices in items are greater than all values in queries	Return a list of 0s for all queries because no item is affordable.
Items with duplicate prices but different beauty values	Sort items by price and then beauty to ensure the most beautiful item is considered first for a given price.
Queries with duplicate values	Process each query independently based on the algorithm, and store the results in order.
Large number of items and queries (scalability)	Use a binary search approach after sorting the items to achieve logarithmic time complexity for each query.
Integer overflow in beauty values when finding max	Use a larger data type (e.g., long) to store intermediate beauty values or limit the range of beauty values in the input.