LC-2070 Medium LeetCode

2070. Most Beautiful Item for Each Query

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 62% Topics: Array, Binary Search, Sorting

Reading material

Arrays & Hashing 12 min Binary Search 12 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn + qlogn)
# Space: O(1)

import bisect


class Solution(object):
    def maximumBeauty(self, items, queries):
        """
        :type items: List[List[int]]
        :type queries: List[int]
        :rtype: List[int]
        """
        items.sort()
        for i in xrange(len(items)-1):
            items[i+1][1] = max(items[i+1][1], items[i][1])
        result = []
        for q in queries:
            i = bisect.bisect_left(items, [q+1])
            result.append(items[i-1][1] if i else 0)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT