Skip to the code
cf.
+25 XP

#261 Earliest One-Time Message

medium

A chat moderation panel wants to show the oldest message id that has been seen exactly once, as messages keep streaming in. Write a class OneTimeMessages:

  • new OneTimeMessages(ids) starts with the ids in ids, in order.
  • add(id) records a new message id.
  • earliest() returns the earliest-arriving id that has been seen exactly once so far, or -1 if there is none.

Each example lists the calls in order, then each call's arguments. The first call creates the object with new OneTimeMessages(…); the output lists what each call returns (null for the constructor and for methods that return nothing).

Example 1

Input: ["OneTimeMessages","earliest","add","earliest","add","earliest","add","earliest"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: [null,2,null,2,null,3,null,-1]

2 is first until a second 2 arrives; then 3 is first until it repeats too, leaving nothing.

Example 2

Input: ["OneTimeMessages","earliest","add","earliest"]
[[[7,7,7]],[],[9],[]]
Output: [null,-1,null,9]

7 repeats, so there is no answer until 9 arrives.

Constraints

  • 0 <= ids.length <= 10^5
  • 1 <= id <= 10^8
  • At most 5 * 10^4 calls in total.
Saved in this browser

Run tries your code on the examples. Submit runs every test, including hidden edge cases, and solves the problem when they all pass.

Ctrl + Enter runs, Ctrl + Shift + Enter submits (⌘ on a Mac).