Longest Uploaded Prefix - Solution & Explanation
Problem Statement
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 ofnvideos.void upload(int video)Uploadsvideoto 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 <= 1051 <= video <= n- All values of
videoare distinct. - At most
2 * 105calls in total will be made touploadandlongest. - At least one call will be made to
longest.
Approach Overview
Problem Overview: You manage a video streaming platform where videos are uploaded in arbitrary order. After each upload, you must return the length of the longest prefix [1..k] where every video in that range has already been uploaded.
Approach 1: Boolean Array + Moving Pointer (O(1) amortized time, O(n) space)
The simplest design keeps a boolean array uploaded of size n + 1. When a video ID is uploaded, mark uploaded[id] = true. Maintain a pointer currentPrefix that tracks the largest prefix already verified. After each upload, advance the pointer while the next index is marked true. This works because the pointer only moves forward and each index is checked once across the entire runtime. Upload is O(1) and prefix updates are amortized O(1), giving excellent performance for this design problem. The idea resembles prefix validation commonly seen in array problems and efficient state tracking.
Approach 2: Ordered Set + Binary Search (O(log n) time, O(n) space)
Another option stores uploaded video IDs inside an ordered set. Each upload inserts the ID into the set in O(log n). To compute the longest prefix, search for the largest k such that every element from 1 through k exists in the set. This can be done by binary searching the range [1, n] and checking membership in the set. The ordered structure ensures fast lookups while binary search narrows the prefix boundary. This method demonstrates how binary search can work with a membership structure like an ordered set.
Although not required for this problem, similar prefix-tracking systems can also be implemented with advanced structures like segment trees or binary indexed trees. Those approaches maintain prefix completeness queries efficiently, but they add unnecessary complexity for this specific scenario.
Recommended for interviews: The boolean array with a moving pointer is the solution interviewers expect. It shows you recognize that the prefix only grows forward and avoids repeated scanning. The ordered set approach demonstrates familiarity with binary search and ordered data structures, but the pointer method is simpler, faster, and closer to the intended design.
Approach 1: Approach 1: Use a boolean array to track uploads.
This approach uses a boolean array to track whether each video has been uploaded. When a video is uploaded, mark it in the boolean array. To find the longest uploaded prefix, traverse the boolean array from the start until you find an unmarked video. The last marked video's index is the length of the longest prefix.
In this Python implementation, we initialize a boolean array where the index represents the video number. When a video is uploaded, we set the corresponding index to True. To determine the longest prefix, we check from the beginning of the boolean array until we encounter an index that's still False. The longest prefix is the highest consecutive index of True values starting from index 1.
Complexity
Time Complexity: O(1) for the upload operation and O(n) for the longest operation in the worst case if longest() is called after each upload sequentially.
Space Complexity: O(n) due to the boolean array used to track uploaded videos.
Approach 2: Approach 2: Use a set to track uploads and binary search for longest.
Instead of a boolean array, use a data structure such as a set to keep track of uploaded videos. In this strategy, update a pointer that keeps track of the longest prefix seen so far. When checking the longest uploaded prefix, use this pointer and verify that all videos before this haven't been uploaded. This allows us to potentially skip already determined parts of the sequence.
In this Python approach, we use a set to store uploaded video IDs since checking membership and adding elements is average O(1). The while loop only updates the longest_prefix when all successive lower numbers have been uploaded.
Complexity
Time Complexity: O(1) on average for both operations due to the set operations.
Space Complexity: O(n) due to storage of uploaded videos in a set.
Approach 3: 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.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Use a boolean array to track uploads. | Time Complexity: O(1) for the upload operation and O(n) for the longest operation in the worst case if longest() is called after each upload sequentially. |
| Approach 2: Use a set to track uploads and binary search for longest. | Time Complexity: O(1) on average for both operations due to the set operations. |
| Simulation | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Boolean Array + Moving Pointer | O(1) amortized per operation | O(n) | Best general solution. Simple implementation and optimal runtime. |
| Ordered Set + Binary Search | O(log n) per operation | O(n) | Useful when working with ordered containers or when practicing binary search on dynamic data. |
Video Solution
Longest Uploaded Prefix || leetcode Biweekly 88 || Leetcode Medium • BinaryMagic • 688 views views
Watch 3 more video solutions →Frequently Asked Questions
Is Longest Uploaded Prefix easy or hard?
How to solve Longest Uploaded Prefix in O(n)?
What is the best approach for Longest Uploaded Prefix?
What data structure is used in Longest Uploaded Prefix?
What is the time complexity of Longest Uploaded Prefix?
Longest Uploaded Prefix Python or Java solution approach?
Is Longest Uploaded Prefix asked at Google, Amazon, or Meta?
Ready to solve this problem?
Practice Longest Uploaded Prefix with our built-in code editor and test cases.
Practice on FleetCode