Practice/Uber/Leetcode 1429. First Unique Number

Leetcode 1429. First Unique Number

CodingMust

Problem

You need to implement a data structure that tracks numbers in a stream and efficiently identifies the first number that appears exactly once. The structure is initialized with a list of numbers and supports two operations:

1. showFirstUnique(): Returns the first number in the stream that appears exactly once. If no such number exists, return -1.
2. add(value): Adds a new number to the end of the stream.

The key challenge is to maintain both the frequency of each number and the order in which they appear, while keeping the showFirstUnique() operation efficient.

Requirements

1. Implement the FirstUnique class with a constructor that accepts an initial array of integers
2. Implement showFirstUnique() to return the first unique number or -1 if none exists
3. Implement add(value) to add a number to the stream
4. The order of numbers matters - "first unique" means the earliest number in insertion order that has appeared exactly once
5. Numbers can be negative, zero, or positive

Constraints

• 1 ≤ nums.length ≤ 105
• 1 ≤ value ≤ 108
• -108 ≤ nums[i] ≤ 108
• At most 50,000 calls will be made to showFirstUnique and add combined
• showFirstUnique should ideally run in O(1) time
• add should run in O(1) time on average

Examples

Example 1:

FirstUnique firstUnique = new FirstUnique([2, 3, 5]); firstUnique.showFirstUnique(); // returns 2 firstUnique.add(5); // the queue is now [2, 3, 5, 5] firstUnique.showFirstUnique(); // returns 2 firstUnique.add(2); // the queue is now [2, 3, 5, 5, 2] firstUnique.showFirstUnique(); // returns 3 firstUnique.add(3); // the queue is now [2, 3, 5, 5, 2, 3] firstUnique.showFirstUnique(); // returns -1

Example 2:

FirstUnique firstUnique = new FirstUnique([10, 20, 30]); firstUnique.showFirstUnique(); // returns 10 firstUnique.add(10); // the queue is now [10, 20, 30, 10] firstUnique.showFirstUnique(); // returns 20 firstUnique.add(20); // the queue is now [10, 20, 30, 10, 20] firstUnique.showFirstUnique(); // returns 30

Example 3:

FirstUnique firstUnique = new FirstUnique([5, 5, 5]); firstUnique.showFirstUnique(); // returns -1 (no unique numbers) firstUnique.add(8); // the queue is now [5, 5, 5, 8] firstUnique.showFirstUnique(); // returns 8