K Highest Ranked Items Within A Price Range - Leetcode Solution

Problem:

You are given a list of items with their prices and ratings. You are also given a price range between minimum price and maximum price. You need to find the k items that have the highest rating within the given price range.

Solution:

One way to solve this problem is by using a max heap. We can iterate through the list of items and add only those items that fall under the given price range to the max heap. Once the max heap has k items, we can remove the item with the lowest rating from the heap, so that only the items with the highest rating remain in the heap. Finally, we can return the top k items from the heap as the solution to the problem.

Here's the complete algorithm:

1. Create an empty max heap.
2. Iterate through the list of items.
3. If the item's price falls within the given price range, add the item to the max heap.
4. If the size of the max heap is greater than k, remove the item with the lowest rating from the heap.
5. Return the top k items from the max heap.

Let's consider an example to understand the algorithm better. Suppose we have the following list of items:

items = [ {"name": "item1", "price": 20, "rating": 4.5}, {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item4", "price": 50, "rating": 4.2}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item6", "price": 70, "rating": 4.1}, {"name": "item7", "price": 80, "rating": 4.9}, {"name": "item8", "price": 90, "rating": 4.3}, ]

Suppose the minimum price is 30, the maximum price is 70, and we need to find the top 3 items within this price range. We can use the algorithm described above to find the solution:

1. Create an empty max heap.
2. Iterate through the list of items.
3. For each item, check if its price falls within the given price range. If it does, add the item to the max heap.
4. After adding the first item, the max heap contains only one item: {"name": "item2", "price": 30, "rating": 4.0}.
5. After adding the second item, the max heap contains two items: {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}.
6. After adding the third item, the max heap contains three items: {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item4", "price": 50, "rating": 4.2}.
7. After adding the fourth item, the max heap contains four items: {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item4", "price": 50, "rating": 4.2}, {"name": "item5", "price": 60, "rating": 4.5}.
8. After adding the fifth item, the max heap contains four items: {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}.
9. After adding the sixth item, the max heap contains four items: {"name": "item2", "price": 30, "rating": 4.0}, {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}.
10. After adding the seventh item, the max heap contains four items: {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}, {"name": "item8", "price": 90, "rating": 4.3}.
11. After adding the eighth item, the max heap contains four items: {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}, {"name": "item8", "price": 90, "rating": 4.3}.
12. The top 3 items in the max heap are: {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}.

Therefore, the solution to the given problem is {"name": "item3", "price": 40, "rating": 4.8}, {"name": "item5", "price": 60, "rating": 4.5}, {"name": "item7", "price": 80, "rating": 4.9}.

Time and Space Complexity:

The time complexity of the algorithm is O(n Log k), where n is the number of items and k is the number of highest-ranked items required. This is because we need to iterate through all the items once, and for each item, we need to add it to the max heap, which takes Log k time. If k is much smaller than n, then the time complexity can be approximated to O(n), as adding items to the max heap takes constant time in this case. The space complexity of the algorithm is O(k), as we need to maintain a max heap of size k.

1