LeetCode 2424: Longest Uploaded Prefix

Explanation

To solve this problem, we can use a set to keep track of the uploaded videos. We can also keep a variable longestPrefix to store the length of the longest uploaded prefix. When a new video is uploaded, we add it to the set and check if the current uploaded sequence is the longest prefix so far. We do this by iterating from 1 to the maximum video number and checking if all videos in that range have been uploaded.

Algorithm:

1. Initialize a set to store uploaded videos and a variable longestPrefix to 0.
2. In the constructor LUPrefix(int n), initialize the set and set longestPrefix to 0.
3. In the upload(int video) method, add the uploaded video to the set.
4. Update longestPrefix by iterating from 1 to the maximum video number and checking if all videos in that range have been uploaded.
5. Return longestPrefix in the longest() method.

Time Complexity:

• The upload and longest operations both take O(n) time, where n is the number of videos.

Space Complexity:

• The space complexity is O(n) to store the uploaded videos.

class LUPrefix {
    Set<Integer> uploadedVideos;
    int longestPrefix;

    public LUPrefix(int n) {
        uploadedVideos = new HashSet<>();
        longestPrefix = 0;
    }

    public void upload(int video) {
        uploadedVideos.add(video);
        for (int i = 1; uploadedVideos.contains(i); i++) {
            longestPrefix = i;
        }
    }

    public int longest() {
        return longestPrefix;
    }
}