We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Uploaded Prefix

Difficulty: Medium

Problem Description

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. We consider i to be an uploaded prefix if all videos in the range 1 to i (inclusive) have been uploaded to the server. The longest uploaded prefix is the maximum value of i that satisfies this definition.

Key Insights

  • Each video is represented by a distinct integer from 1 to n.
  • The longest uploaded prefix is defined based on which videos have been uploaded in the range from 1 to i.
  • Efficiently tracking uploaded videos and calculating the longest prefix requires a data structure that supports both dynamic updates and prefix queries.

Space and Time Complexity

Time Complexity: O(1) for upload and O(n) for longest if implemented naively, but optimal implementations can achieve O(log n) or O(1) for longest. Space Complexity: O(n) for storing uploaded videos.

Solution

To solve the problem, we can use an array to keep track of the uploaded videos and a pointer to track the longest prefix. When a video is uploaded, we mark it as uploaded. The longest function checks from the current longest prefix to see if the next consecutive integers have been uploaded. If they have, we can extend our longest prefix. This way, both operations are efficient, and we avoid unnecessary checks.

Code Solutions

class LUPrefix:

    def __init__(self, n: int):
        self.uploaded = [False] * (n + 1)  # Track uploaded videos
        self.longest_prefix = 0  # Track the longest uploaded prefix

    def upload(self, video: int) -> None:
        self.uploaded[video] = True  # Mark video as uploaded
        # Check for the longest uploaded prefix
        while self.longest_prefix + 1 < len(self.uploaded) and self.uploaded[self.longest_prefix + 1]:
            self.longest_prefix += 1

    def longest(self) -> int:
        return self.longest_prefix  # Return the length of the longest uploaded prefix
← Back to All Questions