Welcome to Subscribe On Youtube

2424. Longest Uploaded Prefix

Description

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.

Solutions

Solution 1: Simulation

We use a variable $r$ to record the current longest prefix of uploaded videos, and an array or hash table $s$ to record the videos that have been uploaded.

Each time a video is uploaded, we set s[video] to true, then loop to check whether s[r + 1] is true. If it is, we update $r$.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the total number of videos.

  • 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();
     */
    
  • 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();
     */
    
  • 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()
    
    
  • type LUPrefix struct {
    	r int
    	s []bool
    }
    
    func Constructor(n int) LUPrefix {
    	return LUPrefix{0, make([]bool, n+1)}
    }
    
    func (this *LUPrefix) Upload(video int) {
    	this.s[video] = true
    	for this.r+1 < len(this.s) && this.s[this.r+1] {
    		this.r++
    	}
    }
    
    func (this *LUPrefix) Longest() int {
    	return this.r
    }
    
    /**
     * Your LUPrefix object will be instantiated and called as such:
     * obj := Constructor(n);
     * obj.Upload(video);
     * param_2 := obj.Longest();
     */
    

All Problems

All Solutions