mediumArraysPattern: General
Optimal Product Selection Solution
Problem Statement
You are given a list of products, where each product is an array containing its rating and price. Implement a function that takes this list and a maximum allowed budget as input, and returns the product with the highest rating that is within the budget. If there are multiple products with the highest rating within the budget, return any one of them.
Examples
Example 1:
Input:{"products":[[5,100],[3,50],[4,80]],"budget":100}
Output:[5,100]
Explanation: Product with the highest rating within the budget is [5, 100]
Example 2:
Input:{"products":[[2,20],[4,40],[6,60]],"budget":50}
Output:[4,40]
Explanation: Product with the highest rating within the budget is [4, 40]
Constraints
- 1 <= number of products <= 1000
- 1 <= product rating <= 5
- 1 <= product price <= 1000
- 1 <= max allowed budget <= 1000
Time: O(n) Space: O(1)
The optimized approach is to use a single pass through the list of products to find the product with the highest rating that is within the budget. This approach has a time complexity of O(n), where n is the number of products. It can be implemented using a simple loop that keeps track of the current highest rating and corresponding product.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def recommend_product(products, budget):
highest_rated_product = None
highest_rating = 0
for product in products:
if product[1] <= budget and product[0] > highest_rating:
highest_rating = product[0]
highest_rated_product = product
return highest_rated_product