LC-2424 Medium LeetCode

2424. Longest Uploaded Prefix

Binary Search Union Find Design Binary Indexed Tree Segment Tree Heap (Priority Queue) Ordered Set

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 54% Topics: Binary Search, Union Find, Design, Binary Indexed Tree, Segment Tree, Heap (Priority Queue), Ordered Set

View full problem on LeetCode

Reading material

Binary Search 12 min Union–Find (DSU) 12 min Design (Data Structures) 14 min

Reference solution (spoiler · python)

# Time:  ctor:    O(1)
#        upload:  O(1), amortized
#        longest: O(1)
# Space: O(n)

# hash table
class LUPrefix(object):

    def __init__(self, n):
        """
        :type n: int
        """
        self.__lookup = set()
        self.__curr = 0

    def upload(self, video):
        """
        :type video: int
        :rtype: None
        """
        self.__lookup.add(video-1)
        while self.__curr in self.__lookup:
            self.__lookup.remove(self.__curr)
            self.__curr += 1

    def longest(self):
        """
        :rtype: int
        """
        return self.__curr

Solution from kamyu104/LeetCode-Solutions · MIT