# Longest Uploaded Prefix
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-uploaded-prefix)
Canonical: https://scaleengineer.com/dsa/problems/longest-uploaded-prefix
**Patterns:** [Design](https://scaleengineer.com/dsa/patterns/design)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** Hash Table, Heap (Priority Queue), Binary Indexed Tree, Segment Tree, Ordered Set
---
## Problem
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
## Using a Boolean Array and Linear Scan in `longest()`
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.
**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.
**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.
### Explanation
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`.

```java
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;
    }
}
```
### 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.

## Optimized Linear Scan by Moving Logic to `upload()`
This approach is a variation of the linear scan method. Instead of calculating the prefix length on-demand in `longest()`, we proactively update it during each `upload` operation. This makes the `longest()` call a simple O(1) lookup.
**Time:** Constructor: `O(n)` to initialize the boolean array.
`upload(video)`: `O(k)` in the worst case, where `k` is the number of newly added consecutive videos. This can be `O(n)` in the worst case for a single call (e.g., uploading videos `n, n-1, ..., 2` and then `1`). The amortized time complexity is `O(1)` as the `while` loop's body executes at most `n` times in total across all calls.
`longest()`: `O(1)` as it just returns a variable. · **Space:** `O(n)` for the boolean array.
**Pros:** `longest()` operation is guaranteed to be `O(1)`, which is ideal for query-heavy scenarios.; Still relatively simple to implement.
**Cons:** The `upload()` operation can be slow in the worst-case for a single call, taking `O(n)` time.
### Explanation
Similar to the previous approach, we use a boolean array `uploaded` and an integer `prefix` to store the current longest prefix length.

The `LUPrefix(n)` constructor initializes these structures.

The `upload(video)` method first marks the video as uploaded. Then, it checks if this new video helps extend the current prefix. It enters a `while` loop, identical to the one in the previous approach's `longest()` method, to increment `prefix` as long as consecutive videos are present.

The `longest()` method now becomes trivial. It simply returns the pre-calculated `prefix` value. This effectively shifts the computational work from `longest()` to `upload()`.

```java
class LUPrefix {
    private boolean[] uploaded;
    private int n;
    private int prefix;

    public LUPrefix(int n) {
        this.n = n;
        // Use n+2 to avoid bounds check for uploaded[prefix+1] when prefix=n
        this.uploaded = new boolean[n + 2];
        this.prefix = 0;
    }

    public void upload(int video) {
        uploaded[video] = true;
        while (uploaded[prefix + 1]) {
            prefix++;
        }
    }

    public int longest() {
        return prefix;
    }
}
```
### Algorithm
- Initialize a boolean array `uploaded` of size `n+2` to `false` and an integer `prefix` to `0`.
- For `upload(video)`:
    - Set `uploaded[video]` to `true`.
    - Use a `while` loop to check if `prefix` can be extended: `while (uploaded[prefix + 1])`.
    - If the condition is met, increment `prefix`.
    - Repeat until the condition is false.
- For `longest()`: Return the current `prefix` value.

## Using a Disjoint Set Union (DSU) Data Structure
This is the most efficient approach in terms of worst-case time complexity per operation. It uses a Disjoint Set Union (DSU) data structure, also known as Union-Find, to group consecutive uploaded videos. The length of the longest prefix is then the size of the set that contains video `1`.
**Time:** Constructor: `O(n)` to initialize the DSU arrays and `uploaded` array.
`upload(video)`: `O(α(n))`, where `α(n)` is the very slow-growing inverse Ackermann function. This is due to the two potential `union` operations.
`longest()`: `O(α(n))` due to the `find` operation. · **Space:** `O(n)` for the `parent`, `sz`, and `uploaded` arrays.
**Pros:** Provides excellent and consistent performance for both `upload` and `longest` operations.; Worst-case time complexity for both operations is nearly constant.
**Cons:** More complex to implement compared to the linear scan approaches.; Slightly higher constant factor overhead due to the DSU logic.
### Explanation
We use three main data structures: a boolean array `uploaded` to track uploaded videos, and two arrays for the DSU, `parent` and `sz` (size). The DSU will manage `n+1` elements (for videos 1 to `n`).

The `LUPrefix(n)` constructor initializes these arrays. Each video starts in its own set.

The `upload(video)` method first marks the video as uploaded. Then, it checks its neighbors (`video - 1` and `video + 1`). If a neighbor has also been uploaded, it performs a `union` operation to merge the sets of the current video and its neighbor. This effectively connects contiguous blocks of uploaded videos.

The `longest()` method checks if video `1` has been uploaded. If not, the prefix is 0. If it has, the length of the longest prefix is simply the size of the set containing video `1`. This can be found by `sz[find(1)]`, where `find(1)` gives the representative of the set containing `1`.

Using path compression and union by size/rank optimizations, the `find` and `union` operations are nearly constant time.

```java
class LUPrefix {
    private int[] parent;
    private int[] sz; // size of component
    private boolean[] uploaded;
    private int n;

    public LUPrefix(int n) {
        this.n = n;
        this.parent = new int[n + 1];
        this.sz = new int[n + 1];
        this.uploaded = new boolean[n + 2]; // Use n+2 for easier neighbor checks
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
            sz[i] = 1;
        }
    }

    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            if (sz[rootI] < sz[rootJ]) {
                int temp = rootI;
                rootI = rootJ;
                rootJ = temp;
            }
            parent[rootJ] = rootI;
            sz[rootI] += sz[rootJ];
        }
    }

    public void upload(int video) {
        uploaded[video] = true;
        // Union with left neighbor if it exists and is uploaded
        if (video > 1 && uploaded[video - 1]) {
            union(video, video - 1);
        }
        // Union with right neighbor if it exists and is uploaded
        if (video < n && uploaded[video + 1]) {
            union(video, video + 1);
        }
    }

    public int longest() {
        if (!uploaded[1]) {
            return 0;
        }
        // The size of the component containing 1 is the longest prefix
        return sz[find(1)];
    }
}
```
### Algorithm
- Initialize a DSU structure for `n+1` elements, with `parent[i] = i` and `size[i] = 1`.
- Initialize a boolean array `uploaded` of size `n+2` to `false`.
- For `upload(video)`:
    - Set `uploaded[video]` to `true`.
    - If `video-1` is uploaded, `union(video, video-1)`.
    - If `video+1` is uploaded, `union(video, video+1)`.
- For `longest()`:
    - If `uploaded[1]` is `false`, return 0.
    - Otherwise, return the size of the set containing 1, which is `size[find(1)]`.

# Solutions
### Java

```java
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(); */
```

### CPP

```cpp
class LUPrefix { public: LUPrefix ( int n ) { } void upload ( int video ) { s . insert ( video ); while ( s . count ( r + 1 )) { ++ r ; } } int longest () { return r ; } private: int r = 0 ; unordered_set < int > s ; }; /** * Your LUPrefix object will be instantiated and called as such: * LUPrefix* obj = new LUPrefix(n); * obj->upload(video); * int param_2 = obj->longest(); */
```

### Python

```python
class LUPrefix : def __init__ ( self , n : int ): self . r = 0 self . s = set () def upload ( self , video : int ) -> None : self . s . add ( video ) while self . r + 1 in self . s : self . r += 1 def longest ( self ) -> int : return self . r # Your LUPrefix object will be instantiated and called as such: # obj = LUPrefix(n) # obj.upload(video) # param_2 = obj.longest()
```