Longest uploaded prefix

October 26, 2022

heap design

Problem URL: Longest uploaded prefix

We will use a longest flag and a list to store all the videos. Since the prefix cannot decrease, it is enough for us to increase it until we reach the number that has not yet been added. We will iterate all videos. For each video, we will check if the video is already in the list. If it is not, we will add it to the list and increase the longest flag. Then we will return the longest flag.

class LUPrefix:
    def __init__(self, n: int):
        self._longest = 0
        self._nums = set()

    def upload(self, video: int) -> None:
        while self._longest+1 in self._nums:
            self._longest += 1

    def longest(self) -> int:
        return self._longest

# Your LUPrefix object will be instantiated and called as such:
# obj = LUPrefix(n)
# obj.upload(video)
# param_2 = obj.longest()

Time Complexity: O(n)
Space Complexity: O(n)