Leetcode 2424: Longest Uploaded Prefix
You are given a stream of n distinct videos, each represented by a unique number from 1 to n. You need to design a data structure that tracks the longest prefix of uploaded videos at any point in time. A prefix is considered uploaded if all videos from 1 to i (inclusive) have been uploaded to the server.
Problem
Approach
Steps
Complexity
Input: The input consists of two types of operations. The first operation initializes the system with n distinct videos. The second operation uploads a specific video to the server. The third operation returns the length of the longest uploaded prefix.
Example: LUPrefix(5); upload(4); longest(); upload(2); longest(); upload(1); longest();
Constraints:
• 1 <= n <= 10^5
• 1 <= video <= n
• All video numbers are distinct.
• At most 2 * 10^5 operations (upload and longest) will be performed.
Output: For each 'longest' operation, return the length of the longest uploaded prefix.
Example: Output: [null, 0, null, 1, null, 3]
Constraints:
• The result should be an integer representing the length of the longest uploaded prefix.
Goal: Track and return the longest sequence of consecutively uploaded videos starting from 1.
Steps:
• 1. Maintain an array or set to track which videos have been uploaded.
• 2. For each 'upload' operation, mark the corresponding video as uploaded.
• 3. After each upload, check how many consecutive videos starting from 1 have been uploaded, and update the longest uploaded prefix.
• 4. For 'longest' operations, simply return the length of the current longest prefix.
Goal: The solution should handle up to 100,000 videos and 200,000 operations efficiently.
Steps:
• Ensure that the operations scale well with large inputs and constraints.
Assumptions:
• All video numbers are distinct and within the range from 1 to n.
• Input: LUPrefix(5); upload(4); longest(); upload(2); longest(); upload(1); longest();
• Explanation: Initially, no videos are uploaded, so the longest prefix is 0. After uploading video 4, no continuous prefix exists, so longest remains 0. After uploading video 2, the longest prefix is still 0, as video 1 hasn't been uploaded yet. Once video 1 is uploaded, the longest prefix becomes [1], and then with videos 1, 2, and 4 uploaded, the longest prefix becomes [1, 2, 3].
Approach: We need to design an efficient way to track the longest uploaded prefix after each 'upload' operation.
Observations:
• We need to keep track of uploaded videos in a way that allows quick determination of the longest continuous prefix.
• An array or set can be used to mark uploaded videos, and we can keep track of the longest prefix by iterating through uploaded videos starting from 1.
Steps:
• 1. Create an array or set to store which videos have been uploaded.
• 2. Maintain a counter i to track the longest prefix starting from 1.
• 3. Each time a video is uploaded, check if the next video in sequence (i) has been uploaded.
• 4. If a video is uploaded that extends the prefix, update i.
• 5. Return the current value of i - 1 for the 'longest' operation.
Empty Inputs:
• There will always be at least one 'longest' operation after initialization, so empty inputs won't occur.
Large Inputs:
• For large inputs, ensure that the algorithm can handle the maximum constraints of 100,000 videos and 200,000 operations.
Special Values:
• Consider cases where the uploaded videos are in a non-sequential order.
Constraints:
• Ensure that the implementation does not exceed time limits, especially for large inputs.
int i;
vector<bool> arr;
LUPrefix(int n) {
arr.resize(n + 1);
i = 1;
}
void upload(int vid) {
arr[vid] = true;
while(i < arr.size() && arr[i]) i++;
}
int longest() {
return i - 1;
}
};
/**
* Your LUPrefix object will be instantiated and called as such:
* LUPrefix* obj = new LUPrefix(n);
* obj->upload(video);
* int param_2 = obj->longest();
1 : Variable Declaration
int i;
Declares an integer variable `i` to keep track of the current index of the longest prefix.
2 : Variable Declaration
vector<bool> arr;
Declares a vector of booleans `arr` to store the uploaded videos' status (true if uploaded, false otherwise).
3 : Constructor
LUPrefix(int n) {
Constructor to initialize the `LUPrefix` object with a given number `n` representing the total number of videos.
4 : Constructor Initialization
arr.resize(n + 1);
Resizes the `arr` vector to accommodate `n+1` elements, ensuring it can hold all video upload statuses.
5 : Constructor Initialization
i = 1;
Initializes `i` to 1, which indicates the starting index for the longest uploaded video.
6 : Function Definition
void upload(int vid) {
Defines the `upload` function, which updates the video upload status for a specific video `vid`.
7 : Upload Logic
arr[vid] = true;
Marks the video at index `vid` as uploaded by setting its status to true.
8 : Upload Logic
while(i < arr.size() && arr[i]) i++;
This loop increments `i` as long as there are uploaded videos, moving through the longest prefix.
9 : Function Definition
int longest() {
Defines the `longest` function, which returns the length of the longest prefix of uploaded videos.
10 : Return Statement
return i - 1;
Returns the length of the longest prefix of uploaded videos by subtracting 1 from `i`.
Best Case: O(1)
Average Case: O(1)
Worst Case: O(n)
Description: The time complexity for 'upload' and 'longest' operations is O(1), while initialization takes O(n) to set up the system.
Best Case: O(n)
Worst Case: O(n)
Description: The space complexity is O(n) due to the need to store the state of uploaded videos.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus