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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Uploaded Prefix

Number: 2512

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

You are given a stream of n videos, each represented by a distinct number from 1 to n. These videos are uploaded in an arbitrary order. At any point in time, you need to determine the longest prefix (i.e., the maximum value i) for which all videos in the range [1, i] have been uploaded.

Key Insights

  • Maintain a pointer (or counter) that represents the smallest video number that has not yet been confirmed as part of the prefix.
  • Use a boolean array (or a hash set) to track which videos have been uploaded.
  • After each upload, check if the uploaded video allows the pointer to move forward, thereby extending the prefix.
  • Since each video is uploaded exactly once, the operations are efficient and only require an amortized constant time per call.

Space and Time Complexity

Time Complexity: O(1) amortized per operation (upload and longest) Space Complexity: O(n) for storing the uploaded status of each video

Solution

To solve the problem, we use an array (or similar data structure) to mark the uploaded videos. We also maintain a pointer, currentPrefix, starting at 1. When a video is uploaded, we mark it as uploaded. Then, we check if the currentPrefix video is uploaded; if it is, we increment the pointer until we reach a video that hasn’t been uploaded. This pointer always indicates the first video missing in the prefix, so the longest uploaded prefix is currentPrefix - 1.

Code Solutions

# Python implementation of LUPrefix

class LUPrefix:
    def __init__(self, n: int):
        # Boolean list to track uploaded videos, using index 1 to n (0-index unused)
        self.n = n
        self.uploaded = [False] * (n + 1)
        # The smallest video index which is not uploaded
        self.currentPrefix = 1

    def upload(self, video: int) -> None:
        # Mark the video as uploaded
        self.uploaded[video] = True
        # Move the currentPrefix pointer forward while videos are available
        while self.currentPrefix <= self.n and self.uploaded[self.currentPrefix]:
            self.currentPrefix += 1

    def longest(self) -> int:
        # Longest uploaded prefix is one less than the current pointer position
        return self.currentPrefix - 1

# Example usage:
# server = LUPrefix(4)
# server.upload(3)
# print(server.longest())  # Output: 0
# server.upload(1)
# print(server.longest())  # Output: 1
# server.upload(2)
# print(server.longest())  # Output: 3
← Back to All Questions