First Unique Number
- 1 min read
- Array
- LC-Medium
3 years ago
Solution
- Just have a hashmap and a queue
- Whenever adding number, increment count and add to queue
- Whenever we want the first unique number, keeping dequeueing from queue until either the queue is empty or element at top of queue has count of 1
- We can do this because we won't be removing any element from the queue
| Time | Space | Explanation |
|---|---|---|
O() | O() |
class FirstUnique:
def __init__(self, nums: List[int]):
self.counts = defaultdict(int)
self.queue = deque()
for num in nums:
self.add(num)
def showFirstUnique(self) -> int:
while self.queue and self.counts[self.queue[0]] > 1:
self.queue.popleft()
if self.queue:
return self.queue[0]
return -1
def add(self, value: int) -> None:
self.queue.append(value)
self.counts[value] += 1