First Unique Number

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.
int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.

Examples

Example 1:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output:
[null,2,null,2,null,3,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2
firstUnique.add(5);            // the queue is now [2,3,5,5]
firstUnique.showFirstUnique(); // return 2
firstUnique.add(2);            // the queue is now [2,3,5,5,2]
firstUnique.showFirstUnique(); // return 3
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3]
firstUnique.showFirstUnique(); // return -1

Example 2:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


Input:
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output:
[null,-1,null,null,null,null,null,17]
Explanation:
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]);
firstUnique.showFirstUnique(); // return -1
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3]
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3]
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7]
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17]
firstUnique.showFirstUnique(); // return 17

Example 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Input:
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output:
[null,809,null,-1]
Explanation:
FirstUnique firstUnique = new FirstUnique([809]);
firstUnique.showFirstUnique(); // return 809
firstUnique.add(809);          // the queue is now [809,809]
firstUnique.showFirstUnique(); // return -1

Constraints:

1 <= nums.length <= 10^5
1 <= nums[i] <= 10^8
1 <= value <= 10^8
At most 50000 calls will be made to showFirstUnique and add.

Solution

Method 1 – Queue and Hash Map

Intuition

We use a queue to maintain the order of numbers and a hash map to count occurrences. The first unique number is the first in the queue with a count of 1.

Approach

Initialize a queue with the numbers and a hash map to count occurrences.
For showFirstUnique, pop elements from the front of the queue until the front is unique (count 1) or the queue is empty.
For add, add the value to the queue and increment its count in the hash map.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class FirstUnique {
    queue<int> q;
    unordered_map<int, int> cnt;
public:
    FirstUnique(vector<int>& nums) {
        for (int n : nums) add(n);
    }
    int showFirstUnique() {
        while (!q.empty() && cnt[q.front()] > 1) q.pop();
        return q.empty() ? -1 : q.front();
    }
    void add(int value) {
        q.push(value);
        cnt[value]++;
    }
};

 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


type FirstUnique struct {
    q   []int
    cnt map[int]int
}

func Constructor(nums []int) FirstUnique {
    f := FirstUnique{cnt: map[int]int{}}
    for _, n := range nums {
        f.Add(n)
    }
    return f
}

func (f *FirstUnique) ShowFirstUnique() int {
    for len(f.q) > 0 && f.cnt[f.q[0]] > 1 {
        f.q = f.q[1:]
    }
    if len(f.q) == 0 {
        return -1
    }
    return f.q[0]
}

func (f *FirstUnique) Add(value int) {
    f.q = append(f.q, value)
    f.cnt[value]++
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


import java.util.*;
class FirstUnique {
    Queue<Integer> q = new LinkedList<>();
    Map<Integer, Integer> cnt = new HashMap<>();
    public FirstUnique(int[] nums) {
        for (int n : nums) add(n);
    }
    public int showFirstUnique() {
        while (!q.isEmpty() && cnt.get(q.peek()) > 1) q.poll();
        return q.isEmpty() ? -1 : q.peek();
    }
    public void add(int value) {
        q.offer(value);
        cnt.put(value, cnt.getOrDefault(value, 0) + 1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class FirstUnique(nums: IntArray) {
    private val q = ArrayDeque<Int>()
    private val cnt = mutableMapOf<Int, Int>()
    init { nums.forEach { add(it) } }
    fun showFirstUnique(): Int {
        while (q.isNotEmpty() && cnt[q.first()]!! > 1) q.removeFirst()
        return q.firstOrNull() ?: -1
    }
    fun add(value: Int) {
        q.addLast(value)
        cnt[value] = cnt.getOrDefault(value, 0) + 1
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14


from collections import deque
class FirstUnique:
    def __init__(self, nums: list[int]):
        self.q = deque()
        self.cnt = {}
        for n in nums:
            self.add(n)
    def showFirstUnique(self) -> int:
        while self.q and self.cnt[self.q[0]] > 1:
            self.q.popleft()
        return self.q[0] if self.q else -1
    def add(self, value: int) -> None:
        self.q.append(value)
        self.cnt[value] = self.cnt.get(value, 0) + 1

 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


use std::collections::{VecDeque, HashMap};
struct FirstUnique {
    q: VecDeque<i32>,
    cnt: HashMap<i32, i32>,
}
impl FirstUnique {
    fn new(nums: Vec<i32>) -> Self {
        let mut f = FirstUnique { q: VecDeque::new(), cnt: HashMap::new() };
        for n in nums { f.add(n); }
        f
    }
    fn show_first_unique(&mut self) -> i32 {
        while let Some(&x) = self.q.front() {
            if *self.cnt.get(&x).unwrap() > 1 {
                self.q.pop_front();
            } else {
                return x;
            }
        }
        -1
    }
    fn add(&mut self, value: i32) {
        self.q.push_back(value);
        *self.cnt.entry(value).or_insert(0) += 1;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class FirstUnique {
    private q: number[] = [];
    private cnt = new Map<number, number>();
    constructor(nums: number[]) {
        for (const n of nums) this.add(n);
    }
    showFirstUnique(): number {
        while (this.q.length && this.cnt.get(this.q[0])! > 1) this.q.shift();
        return this.q.length ? this.q[0] : -1;
    }
    add(value: number): void {
        this.q.push(value);
        this.cnt.set(value, (this.cnt.get(value) ?? 0) + 1);
    }
}

Complexity

⏰ Time complexity: O(1) amortized per operation, since each element is added and removed from the queue at most once.
🧺 Space complexity: O(N), where N is the number of elements added.

Problem#

Examples#

Solution#

Method 1 – Queue and Hash Map#

Intuition#

Approach#

Code#

Complexity#