Scale Engineer

Longest Uploaded Prefix

Med
#2208Time: Constructor: `O(n)` to initialize the boolean array. `upload(video)`: `O(1)` for a single array write operation. `longest()`: `O(k)` in the worst case for a single call, where `k` is the number of newly added consecutive videos that extend the prefix. In the absolute worst case, this can be `O(n)`. However, the total work done by the `while` loop across all calls to `longest()` is `O(n)`, making the amortized time complexity `O(1)`.Space: `O(n)` to store the `uploaded` status for all `n` videos.
Patterns
Design
Algorithms
Binary SearchUnion Find
Data structures
Hash TableHeap (Priority Queue)Binary Indexed TreeSegment TreeOrdered Set

Prompt

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 <= 105
  • 1 <= video <= n
  • All values of video are distinct.
  • At most 2 * 105 calls in total will be made to upload and longest.
  • At least one call will be made to longest.

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses a boolean array to keep track of the uploaded videos. The upload operation is a simple O(1) update to this array. The longest operation finds the prefix length by iterating from the last known prefix length and checking for consecutive uploaded videos.

Algorithm

  • Initialize a boolean array uploaded of size n+1 to false and an integer prefix to 0.
  • For upload(video): Set uploaded[video] to true.
  • For longest():
    • Use a while loop to check if prefix can be extended.
    • The condition is prefix < n and uploaded[prefix + 1] == true.
    • If the condition is met, increment prefix.
    • Repeat until the condition is false.
    • Return the final prefix value.

Walkthrough

We initialize a boolean array, say uploaded, of size n + 1. uploaded[i] will be true if video i has been uploaded, and false otherwise. We also maintain a variable, prefix, initialized to 0, which stores the length of the longest uploaded prefix found so far. This helps to avoid re-scanning from 1 every time.

The LUPrefix(n) constructor initializes this uploaded array and the prefix variable.

The upload(video) method simply marks the corresponding video as uploaded by setting uploaded[video] = true.

The longest() method contains the core logic. It enters a loop that starts checking from prefix + 1. As long as the next consecutive video (uploaded[prefix + 1]) is found to be uploaded, it increments prefix. The loop stops when it finds a video that has not been uploaded yet. Finally, it returns the current value of prefix.

class LUPrefix {    private boolean[] uploaded;    private int n;    private int prefix;     public LUPrefix(int n) {        this.n = n;        this.uploaded = new boolean[n + 1];        this.prefix = 0;    }     public void upload(int video) {        uploaded[video] = true;    }     public int longest() {        while (prefix < n && uploaded[prefix + 1]) {            prefix++;        }        return prefix;    }}

Complexity

Time

Constructor: `O(n)` to initialize the boolean array. `upload(video)`: `O(1)` for a single array write operation. `longest()`: `O(k)` in the worst case for a single call, where `k` is the number of newly added consecutive videos that extend the prefix. In the absolute worst case, this can be `O(n)`. However, the total work done by the `while` loop across all calls to `longest()` is `O(n)`, making the amortized time complexity `O(1)`.

Space

`O(n)` to store the `uploaded` status for all `n` videos.

Trade-offs

Pros

  • Simple to understand and implement.

  • upload operation is extremely fast (O(1)).

Cons

  • The longest() operation can be slow in the worst-case for a single call, potentially taking O(n) time.

Solutions

class LUPrefix { private int r ; private Set < Integer > s = new HashSet <>(); public LUPrefix ( int n ) { } public void upload ( int video ) { s . add ( video ); while ( s . contains ( r + 1 )) { ++ r ; } } public int longest () { return r ; } } /** * Your LUPrefix object will be instantiated and called as such: * LUPrefix obj = new LUPrefix(n); * obj.upload(video); * int param_2 = obj.longest(); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem