Problem statement

https://binarysearch.com/problems/Earliest-Uniques-in-a-Stream/

Solution

Keep deque for all nums and also keep indicator if value is unique. To find the earliest unique, we need to first delete from our queue all bad elements.

Complexity

It is amortized O(1) for time for operations and O(n) for space.

Code

class EarliestUnique:
    def __init__(self, nums):
        self.q = deque(nums)
        self.unique = {}
        for num in nums: self.add(num)

    def add(self, value):
        if value not in self.unique:
            self.unique[value] = True
            self.q.append(value)
        else:
            self.unique[value] = False

    def earliestUnique(self):
        while self.q and not self.unique[self.q[0]]:
            self.q.popleft()
        return self.q[0] if self.q else -1