Skip to content

2424. Longest Uploaded Prefix 👍

  • Time:
    • Constructor: $O(1)$
    • upload(video: int): $O(1)$
    • longest(): $O(1)$
  • Space: $O(|\texttt{upload()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
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