Longest Uploaded Prefix

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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

Solution

Method 1 – Greedy with Pointer Tracking

Intuition

We want to efficiently track the longest prefix of uploaded videos. By keeping a pointer to the current prefix and a set or array to mark uploaded videos, we can always check if the next prefix is available and increment the pointer.

Approach

Use a boolean array (or set) to mark which videos have been uploaded.
Maintain a pointer cur for the current longest prefix.
On each upload, mark the video as uploaded.
While the next video in sequence is uploaded, increment the prefix pointer.
The longest method returns the current prefix pointer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class LUPrefix {
    vector<bool> uploaded;
    int cur;
public:
    LUPrefix(int n) : uploaded(n+2, false), cur(0) {}
    void upload(int video) {
        uploaded[video] = true;
        while (uploaded[cur+1]) ++cur;
    }
    int longest() { return cur; }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


type LUPrefix struct {
    uploaded []bool
    cur int
}
func Constructor(n int) LUPrefix {
    return LUPrefix{make([]bool, n+2), 0}
}
func (this *LUPrefix) Upload(video int) {
    this.uploaded[video] = true
    for this.uploaded[this.cur+1] {
        this.cur++
    }
}
func (this *LUPrefix) Longest() int {
    return this.cur
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


class LUPrefix {
    boolean[] uploaded;
    int cur = 0;
    public LUPrefix(int n) {
        uploaded = new boolean[n+2];
    }
    public void upload(int video) {
        uploaded[video] = true;
        while (uploaded[cur+1]) cur++;
    }
    public int longest() {
        return cur;
    }
}

1
2
3
4
5
6
7
8
9


class LUPrefix(n: Int) {
    private val uploaded = BooleanArray(n+2)
    private var cur = 0
    fun upload(video: Int) {
        uploaded[video] = true
        while (uploaded[cur+1]) cur++
    }
    fun longest(): Int = cur
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class LUPrefix:
    def __init__(self, n: int):
        self.uploaded = [False] * (n+2)
        self.cur = 0
    def upload(self, video: int) -> None:
        self.uploaded[video] = True
        while self.uploaded[self.cur+1]:
            self.cur += 1
    def longest(self) -> int:
        return self.cur

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


struct LUPrefix {
    uploaded: Vec<bool>,
    cur: usize,
}
impl LUPrefix {
    fn new(n: i32) -> Self {
        Self { uploaded: vec![false; n as usize + 2], cur: 0 }
    }
    fn upload(&mut self, video: i32) {
        self.uploaded[video as usize] = true;
        while self.uploaded[self.cur+1] {
            self.cur += 1;
        }
    }
    fn longest(&self) -> i32 {
        self.cur as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class LUPrefix {
    private uploaded: boolean[];
    private cur: number;
    constructor(n: number) {
        this.uploaded = new Array(n+2).fill(false);
        this.cur = 0;
    }
    upload(video: number): void {
        this.uploaded[video] = true;
        while (this.uploaded[this.cur+1]) this.cur++;
    }
    longest(): number {
        return this.cur;
    }
}

Complexity

⏰ Time complexity: O(1) per operation, as each video is processed once.
🧺 Space complexity: O(n), for the uploaded array.

Problem#

Examples#

Example 1#

Constraints#

Solution#

Method 1 – Greedy with Pointer Tracking#

Intuition#

Approach#

Code#

Complexity#