2424. Longest Uploaded Prefix LeetCode Solution

In this guide, you will get 2424. Longest Uploaded Prefix LeetCode Solution with the best time and space complexity. The solution to Longest Uploaded Prefix problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Longest Uploaded Prefix solution in C++
Longest Uploaded Prefix solution in Java
Longest Uploaded Prefix solution in Python
Additional Resources

2424. Longest Uploaded Prefix LeetCode Solution image

Problem Statement of Longest Uploaded Prefix

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.

Complexity Analysis

Time Complexity: O(1)
Space Complexity: O(|\texttt{upload()}|)

2424. Longest Uploaded Prefix LeetCode Solution in C++

class LUPrefix {
 public:
  LUPrefix(int n) {}

  void upload(int video) {
    seen.insert(video);
    while (seen.contains(longestPrefix + 1))
      ++longestPrefix;
  }

  int longest() {
    return longestPrefix;
  }

 private:
  unordered_set<int> seen;
  int longestPrefix = 0;
};
/* code provided by PROGIEZ */

2424. Longest Uploaded Prefix LeetCode Solution in Java

class LUPrefix {
  public LUPrefix(int n) {}

  public void upload(int video) {
    seen.add(video);
    while (seen.contains(longestPrefix + 1))
      ++longestPrefix;
  }

  public int longest() {
    return longestPrefix;
  }

  private Set<Integer> seen = new HashSet<>();
  private int longestPrefix = 0;
}
// code provided by PROGIEZ

2424. Longest Uploaded Prefix LeetCode Solution in Python

class LUPrefix:
  def __init__(self, n: int):
    self.seen = set()
    self.longestPrefix = 0

  def upload(self, video: int) -> None:
    self.seen.add(video)
    while self.longestPrefix + 1 in self.seen:
      self.longestPrefix += 1

  def longest(self) -> int:
    return self.longestPrefix
 # code by PROGIEZ