Watch 4 video solutions for Longest Uploaded Prefix, a medium level problem involving Binary Search, Union Find, Design. This walkthrough by BinaryMagic has 672 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 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
["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 <= nvideo are distinct.2 * 105 calls in total will be made to upload and longest.longest.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 | 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. |