Learn AI Create the Future — with Pranay
Main site

LeetCode solutions

2179. Most Beautiful Item for Each Query

My accepted Python solution to LeetCode problem 2179, Most Beautiful Item for Each Query, running in 304ms.

  • Difficulty: Medium
  • Python
  • Runtime 304ms
  • Memory 64.4MB

Read the problem on LeetCode View on GitHub

The problem statement is LeetCode’s and stays on their site. What follows is my accepted solution.

Python

Accepted on LeetCode — runtime 304ms, memory 64.4MB, accepted 2025-12-29.

python
class Solution:
    def maximumBeauty(self, items: List[List[int]], queries: List[int]) -> List[int]:
        # Sort items by price, then precompute max beauty up to each price
        # Binary search for each query
        # Time: O(n log n + m log n), Space: O(n)
        
        # Sort by price
        items.sort()
        
        # Precompute maximum beauty up to each index
        max_beauty_at = []
        max_so_far = 0
        for price, beauty in items:
            max_so_far = max(max_so_far, beauty)
            max_beauty_at.append((price, max_so_far))
        
        def binary_search(query):
            # Find rightmost price <= query
            left, right = 0, len(max_beauty_at) - 1
            result = 0
            while left <= right:
                mid = (left + right) // 2
                if max_beauty_at[mid][0] <= query:
                    result = max_beauty_at[mid][1]
                    left = mid + 1
                else:
                    right = mid - 1
            return result
        
        return [binary_search(q) for q in queries]

Source