Skip to content

1429. First Unique Number 👍

  • Time:
    • Constructor: $O(n)$
    • showFirstUnique(): $O(1)$
    • add(value: int): $O(1)$
  • Space: $O(|\texttt{nums}| + |\texttt{add()}|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class FirstUnique {
 public:
  FirstUnique(vector<int>& nums) {
    for (const int num : nums)
      add(num);
  }

  int showFirstUnique() {
    return unique.empty() ? -1 : unique.front();
  }

  void add(int value) {
    const auto it = valueToIterator.find(value);
    if (it == valueToIterator.cend()) {
      unique.push_back(value);
      valueToIterator[value] = prev(unique.end());
    } else if (it->second != unique.end()) {
      // We have added this value before, and this is the second time we're
      // adding it. So, erase the value from `unique` and mark it as erased.
      unique.erase(it->second);
      valueToIterator[value] = unique.end();
    }
  }

 private:
  list<int> unique;
  unordered_map<int, list<int>::iterator> valueToIterator;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class FirstUnique {
  public FirstUnique(int[] nums) {
    for (final int num : nums)
      add(num);
  }

  public int showFirstUnique() {
    return unique.isEmpty() ? -1 : unique.iterator().next();
  }

  public void add(int value) {
    if (!seen.contains(value)) {
      unique.add(value);
      seen.add(value);
    } else if (unique.contains(value)) {
      // We have added this value before, and this is the second time we're
      // adding it. So, erase the value from `unique`.
      unique.remove(value);
    }
  }

  private Set<Integer> seen = new HashSet<>();
  private Set<Integer> unique = new LinkedHashSet<>();
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class FirstUnique:
  def __init__(self, nums: list[int]):
    self.seen = set()
    self.unique = {}
    for num in nums:
      self.add(num)

  def showFirstUnique(self) -> int:
    return next(iter(self.unique), -1)

  def add(self, value: int) -> None:
    if value not in self.seen:
      self.seen.add(value)
      self.unique[value] = 1
    elif value in self.unique:
      # We have added this value before, and this is the second time we're
      # adding it. So, erase the value from `unique`.
      self.unique.pop(value)