Problem statement

A stream of n videos, numbered 1 to n, is being uploaded to a server — in any order. The longest uploaded prefix is the largest i such that videos 1, 2, …, i have all been uploaded (0 if video 1 has not been).

Write the class LUPrefix:

• LUPrefix(int n) sets up a stream of n videos, none uploaded yet.
• void upload(int video) uploads video.
• int longest() returns the length of the longest uploaded prefix.

The judge calls the methods in the order listed in the first input line, with the arguments in the second; the expected output holds each call's result, null for the constructor and for every method that returns nothing.

Example 1

Input: ["LUPrefix","upload","longest","upload","longest","upload","longest"]
[[4],[3],[],[1],[],[2],[]]
Output: [null,null,0,null,1,null,3]
Explanation: Video 3 alone gives no prefix (video 1 is missing). After video 1 the prefix is 1; once video 2 arrives, 1, 2 and 3 are all there, so it jumps to 3.

Example 2

Input: ["LUPrefix","longest","upload","longest"]
[[1],[],[1],[]]
Output: [null,0,null,1]
Explanation: With a single video, the prefix is 0 until it is uploaded and 1 afterwards.

Constraints

• 1 <= video <= n <= 10^5
• All values of video are distinct
• At most 2 * 10^5 calls are made in total to upload and longest
• At least one call is made to longest

Hints for Longest Uploaded Prefix

1. Hint 1

   The answer never goes down: once videos 1..i are all uploaded they stay uploaded.

2. Hint 2

   Keep a pointer p to the current prefix length and a boolean per video.

3. Hint 3

   After an upload, advance p while video p + 1 is uploaded. Each video is stepped over at most once in total.

How to solve Longest Uploaded Prefix

The prefix length only grows, so it can be maintained by a pointer that walks forward over uploaded videos. Every video is passed by the pointer at most once, so the whole stream costs O(n) in total.

Approach

1. Keep seen[1..n+1] (all false) and prefix = 0.
2. upload(video): set seen[video] = true, then while seen[prefix + 1] is true, increase prefix.
3. longest(): return prefix.

Why it works

The invariant is that prefix is the largest i with videos 1..i uploaded. An upload can only extend that run, and the loop extends it exactly as far as consecutive uploaded videos reach; video prefix + 1 is then missing, so the run cannot be longer.

Complexity

• Time — O(1) amortised per call — O(n + q) in total
• Space — O(n)

Pitfalls

• Size the array n + 2 (or bound the loop by n) so checking video prefix + 1 after the last video stays in range.
• Recomputing the prefix from 1 on every longest call is O(n) per call and too slow for 2 * 10^5 calls.

Reference solution

Python

class LUPrefix:

    def __init__(self, n: int):
        self.seen = [False] * (n + 2)
        self.prefix = 0  # videos 1..prefix are all uploaded

    def upload(self, video: int) -> None:
        self.seen[video] = True
        while self.seen[self.prefix + 1]:
            self.prefix += 1

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

Java

class LUPrefix {
    private boolean[] seen;
    private int prefix = 0; // videos 1..prefix are all uploaded

    public LUPrefix(int n) {
        seen = new boolean[n + 2];
    }

    public void upload(int video) {
        seen[video] = true;
        while (seen[prefix + 1]) prefix++;
    }

    public int longest() {
        return prefix;
    }
}

C++

class LUPrefix {
    vector<char> seen;
    int prefix = 0; // videos 1..prefix are all uploaded
public:
    LUPrefix(int n) : seen(n + 2, 0) {}

    void upload(int video) {
        seen[video] = 1;
        while (seen[prefix + 1]) prefix++;
    }

    int longest() {
        return prefix;
    }
};

JavaScript

var LUPrefix = function(n) {
    this.seen = new Uint8Array(n + 2);
    this.prefix = 0; // videos 1..prefix are all uploaded
};

LUPrefix.prototype.upload = function(video) {
    this.seen[video] = 1;
    while (this.seen[this.prefix + 1]) this.prefix++;
};

LUPrefix.prototype.longest = function() {
    return this.prefix;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More hash table problems

• Implement Router Medium
• Design Task Manager Medium
• Frequency Tracker Medium
• Find Consecutive Integers from a Data Stream Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium