Longest uploaded prefix

Hash Table Binary Search Union-Find Design Binary Indexed Tree Segment Tree Heap (Priority Queue) Ordered Set

54.8% acceptance

Feb 23, 2026

386

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

pub struct LUPrefix {
  uploaded: Vec<bool>,
  prefix: usize,
}

impl LUPrefix {
  pub fn new(n: i32) -> Self {
    LUPrefix {
      uploaded: vec![false; n as usize + 1],
      prefix: 0,
    }
  }

  pub fn upload(&mut self, video: i32) {
    self.uploaded[video as usize] = true;
  }

  pub fn longest(&mut self) -> i32 {
    while self.prefix + 1 < self.uploaded.len() && self.uploaded[self.prefix + 1] {
      self.prefix += 1;
    }
    self.prefix as i32
  }
}