##### Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/2424.html

• Difficulty: Medium.
• Related Topics: .
• Similar Questions: Design an Ordered Stream.

## 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.

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.

Implement the LUPrefixclass:

• LUPrefix(int n) Initializes the object for a stream of n videos.

• void upload(int video) Uploads video to the server.

• int longest() Returns the length of the longest uploaded prefix defined above.

Example 1:

Input
[, , [], , [], , []]
Output
[null, null, 0, null, 1, null, 3]

Explanation
LUPrefix server = new LUPrefix(4);   // Initialize a stream of 4 videos.
server.longest();                    // Since video 1 has not been uploaded yet, there is no prefix.
// So, we return 0.
server.longest();                    // The prefix  is the longest uploaded prefix, so we return 1.
server.longest();                    // The prefix [1,2,3] is the longest uploaded prefix, so we return 3.


Constraints:

• 1 <= n <= 10^5

• 1 <= video <= 10^5

• All values of video are distinct.

• At most 2 * 10^5 calls in total will be made to upload and longest.

• At least one call will be made to longest.

## Solution (Java, C++, Python)

• class LUPrefix {
private int r;
private Set<Integer> s = new HashSet<>();

public LUPrefix(int n) {

}

while (s.contains(r + 1)) {
++r;
}
}

public int longest() {
return r;
}
}

/**
* Your LUPrefix object will be instantiated and called as such:
* LUPrefix obj = new LUPrefix(n);
* int param_2 = obj.longest();
*/

• class LUPrefix {
public:
LUPrefix(int n) {

}

s.insert(video);
while (s.count(r + 1)) {
++r;
}
}

int longest() {
return r;
}

private:
int r = 0;
unordered_set<int> s;
};

/**
* Your LUPrefix object will be instantiated and called as such:
* LUPrefix* obj = new LUPrefix(n);
* int param_2 = obj->longest();
*/

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

def upload(self, video: int) -> None:
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)
# param_2 = obj.longest()


• type LUPrefix struct {
r int
s []bool
}

func Constructor(n int) LUPrefix {
return LUPrefix{0, make([]bool, n+1)}
}

func (this *LUPrefix) Upload(video int) {
this.s[video] = true
for this.r+1 < len(this.s) && this.s[this.r+1] {
this.r++
}
}

func (this *LUPrefix) Longest() int {
return this.r
}

/**
* Your LUPrefix object will be instantiated and called as such:
* obj := Constructor(n);
* param_2 := obj.Longest();
*/


Explain:

nope.

Complexity:

• Time complexity : O(n).
• Space complexity : O(n).