problemmediumalgorithmsleetcode-1429leetcode 1429leetcode1429

First Unique Number

MediumUpdated: Aug 2, 2025
Practice on:
LeetCode

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:

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:

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:

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

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

Code

C++
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]++;
    }
};
Go
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]++
}
Java
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);
    }
}
Kotlin
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
    }
}
Python
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
Rust
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;
    }
}
TypeScript
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.

Comments