Longest Uploaded Prefix — LeetCode 2424 Python Solution

The problem

You are given a stream of n videos, each represented by a distinct number from 1 to n that you need to "upload" to a server. You need to implement a data structure that calculates the length of the longest uploaded prefix at various points in the upload process.

Example

Input

["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]

Output

[null, null, 0, null, 1, null, 3]

Explanation

LUPrefix server = new LUPrefix(4); // Initialize a stream of 4 videos.

Python solution

class LUPrefix:
    def __init__(self, n: int):
        self.r = 0
        self.s = set()

    def upload(self, video: int) -> None:
        self.s.add(video)
        while self.r + 1 in self.s:
            self.r += 1

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


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

Complexity

Pattern: Union-Find

Merge groups and ask whether two things are connected, both in near-constant time. LeetCode 2424. Longest Uploaded Prefix is filed here because LeetCode tags it Union Find, which is the vocabulary this hub collects.

The union-find guide has the Python template for the pattern and the 83 LeetCode problems that use it.

Related problems