#2424
Longest Uploaded Prefix
specialist · 805 · lc medium +31 · 54.8% accepted · 386 likes · top 48%
Description
You receive a stream of n video IDs, each a distinct integer from 1 to n. Implement a data structure to track the longest uploaded prefix after each upload.
A prefix [1, 2, ..., i] is uploaded when all videos from 1 to i have been received.
Implement the LUPrefix class:
- LUPrefix(int n) initializes the tracker for n videos.
- void upload(int video) records that video video has been uploaded.
- int longest() returns the length of the longest uploaded prefix.
Example 1:
Input
["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"]
[[4], [3], [], [1], [], [2], []]
Output
[null, null, 0, null, 1, null, 3]
Example 2:
Explanation
LUPrefix server = new LUPrefix(4); // Initialize a stream of 4 videos.
server.upload(3); // Upload video 3.
server.longest(); // Since video 1 has not been uploaded yet, there is no prefix.
// So, we return 0.
server.upload(1); // Upload video 1.
server.longest(); // The prefix [1] is the longest uploaded prefix, so we return 1.
server.upload(2); // Upload video 2.
server.longest(); // The prefix [1,2,3] is the longest uploaded prefix, so we return 3.
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16