We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Most Beautiful Item for Each Query

Number: 2179

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Postmates, razorpay

Problem Description

Given a list of items where each item has a price and a beauty value, and a list of queries representing maximum price limits, the goal is to determine for each query the maximum beauty among the items whose price is less than or equal to the query value. If no item qualifies for a query, the answer is 0.

Key Insights

  • Sort the items by their price in ascending order.
  • Process queries in sorted order (keeping track of their original indices) to efficiently update the maximum beauty seen so far.
  • Use a two-pointer approach: advance through the sorted items while the item's price is less than or equal to the current query value.
  • Store the maximum beauty encountered and assign it to the corresponding query result.

Space and Time Complexity

Time Complexity: O(n log n + q log q + (n + q)), where n is the number of items and q is the number of queries.
Space Complexity: O(n + q) for storing the sorted queries and the result array.

Solution

The solution involves first sorting the items by price and the queries by their query value while preserving indices. Initialize pointers for both arrays and a variable for tracking the current maximum beauty. For each query, move the pointer through the items as long as the item price is within the query limit and update the maximum beauty accordingly. Finally, assign the maximum beauty to the query's result, ensuring the output order matches the original query order.

Code Solutions

def mostBeautifulItemForEachQuery(items, queries):
    # Sort items by price
    items.sort(key=lambda x: x[0])
    # Create list of queries with their original indices
    sorted_queries = sorted(enumerate(queries), key=lambda x: x[1])
    # Initialize the answer list with zeros
    ans = [0] * len(queries)
    max_beauty = 0
    i = 0  # Pointer for items
    n = len(items)
    
    # Process each query in ascending order of query value
    for idx, q in sorted_queries:
        # Advance the pointer while items are within the price limit
        while i < n and items[i][0] <= q:
            max_beauty = max(max_beauty, items[i][1])
            i += 1
        # Set the result for the current query using its original index
        ans[idx] = max_beauty
    return ans

# Example usage:
items = [[1,2],[3,2],[2,4],[5,6],[3,5]]
queries = [1,2,3,4,5,6]
print(mostBeautifulItemForEachQuery(items, queries))
← Back to All Questions