2424. Longest Uploaded Prefix

Problem¶

Track uploads of distinct video IDs from 1 to n. After any upload, return the largest k such that every video from 1 through k has been uploaded; return 0 if video 1 is missing.

n = 4
Upload       Uploaded IDs       longest()
(initial)    {}                 0
3            {3}                0
1            {1, 3}             1
2            {1, 2, 3}          3

class LUPrefix:
    def __init__(self, n: int):
        pass

    def upload(self, video: int) -> None:
        pass

    def longest(self) -> int:
        pass

Key trick¶

Keep a pointer to the prefix end and advance it while the next video is uploaded; the pointer never moves backward.

Trap¶

One upload can advance the prefix by several positions, so use a loop rather than a single increment. An upload is amortized \(O(1)\), not worst-case \(O(1)\).

Why is it interesting?¶

A monotonic pointer turns repeated prefix scans into linear total work, even when uploads arrive out of order.

Python solution¶

class LUPrefix:
    def __init__(self, n: int):
        # Index by video ID; n + 1 is an unuploaded sentinel.
        self.uploaded = bytearray(n + 2)
        self.prefix_len = 0

    def upload(self, video: int) -> None:
        self.uploaded[video] = 1
        while self.uploaded[self.prefix_len + 1]:
            self.prefix_len += 1

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

Initialization: \(O(n)\) time.
upload: amortized \(O(1)\) time; worst-case \(O(n)\).
longest: \(O(1)\) time.
Space: \(O(n)\).

Comment on my solution¶

Your solution is correct and interview-ready: the zero-based indexing and boundary check are consistent, and your conditional avoids unnecessary scans.

The complexity comment needs one correction: uploads take \(O(n)\) total across all videos, giving \(O(1)\) amortized per upload, while longest() takes \(O(1)\).

# Ideas:
# up 3
# [. . 3]
# l -> 0
# up 1
# [1 . 3]
# l -> 1
# up 2
# [1 2 3]
# l -> 3
#
# - keep pointer prefix_end on the end of the longest prefix
#   - when the video prefix_end + 1 is uploaded scan from that
#     video up to the new prefix end
#     - this gives O(1) longest() and amortized O(n) upload()
#       because each video is scanned at most 1
#
# [1 2 3 . 5 6 . . 7]

# WORKS
class LUPrefix:
    def __init__(self, n: int):
        self.uploaded = [False] * n
        self.prefix_len = 0

    def upload(self, video: int) -> None:
        self.uploaded[video - 1] = True
        if video - 1 == self.prefix_len:
            self.prefix_len += 1
            while self.prefix_len < len(self.uploaded) and self.uploaded[self.prefix_len]:
                self.prefix_len += 1

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