2424. Longest Uploaded Prefix
Description
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 LUPrefix
class:
LUPrefix(int n)
Initializes the object for a stream ofn
videos.void upload(int video)
Uploadsvideo
to the server.int longest()
Returns the length of the longest uploaded prefix defined above.
Example 1:
Input ["LUPrefix", "upload", "longest", "upload", "longest", "upload", "longest"] [[4], [3], [], [1], [], [2], []] Output [null, null, 0, null, 1, null, 3] 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.
Constraints:
1 <= n <= 105
1 <= video <= n
- All values of
video
are distinct. - At most
2 * 105
calls in total will be made toupload
andlongest
. - At least one call will be made to
longest
.
Solutions
Solution 1: Simulation
We use a variable $r$ to record the current longest prefix of uploaded videos, and an array or hash table $s$ to record the videos that have been uploaded.
Each time a video is uploaded, we set s[video]
to true
, then loop to check whether s[r + 1]
is true
. If it is, we update $r$.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the total number of videos.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
|