MediumNo. 1429LeetCode Premium
First Unique Number — LeetCode 1429 Python Solution
- Pattern
- Stack
- Topics
- Design, Queue, Array, Hash Table, Data Stream
- Reading time
- 4 min
- Source
- leetcode.com
The problem
You have a queue of integers, you need to retrieve the first unique integer in the queue. Implement the FirstUnique class: FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
Example
- Input
- ["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
- Output
- [null,2,null,2,null,3,null,-1]
- Explanation
- FirstUnique firstUnique = new FirstUnique([2,3,5]);
Python solution
class FirstUnique:
def __init__(self, nums: List[int]):
self.cnt = Counter(nums)
self.unique = OrderedDict({v: 1 for v in nums if self.cnt[v] == 1})
def showFirstUnique(self) -> int:
return -1 if not self.unique else next(v for v in self.unique.keys())
def add(self, value: int) -> None:
self.cnt[value] += 1
if self.cnt[value] == 1:
self.unique[value] = 1
elif value in self.unique:
self.unique.pop(value)
# Your FirstUnique object will be instantiated and called as such:
# obj = FirstUnique(nums)
# param_1 = obj.showFirstUnique()
# obj.add(value)Complexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Stack
When the most recent unresolved thing is the one that matters, use a stack. LeetCode 1429. First Unique Number is filed here because LeetCode tags it Queue, which is the vocabulary this hub collects.
The stack guide has the Python template for the pattern and the 194 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 1656 | Design an Ordered Stream | Easy |
| 2526 | Find Consecutive Integers from a Data Stream | Medium |
| 0352 | Data Stream as Disjoint Intervals | Hard |
| 0380 | Insert Delete GetRandom O(1) | Medium |
| 0381 | Insert Delete GetRandom O(1) - Duplicates allowed | Hard |
| 0705 | Design HashSet | Easy |
Frequently asked questions
- How hard is LeetCode 1429. First Unique Number?
LeetCode 1429. First Unique Number is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1429. First Unique Number?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1429. First Unique Number?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1429. First Unique Number cover?
LeetCode 1429. First Unique Number is tagged Design, Queue, Array, Hash Table and Data Stream on LeetCode.
- Is LeetCode 1429. First Unique Number a premium problem?
Yes. LeetCode 1429. First Unique Number is a LeetCode Premium problem, so the full statement and test cases require a paid LeetCode subscription.