We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

First Unique Number

Number: 1366

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a stream (or queue) of integers, design a class that efficiently supports finding the first unique integer in the queue as well as adding new numbers to the queue. The class should support initialization with an array of numbers, a method to display the first unique number (or -1 if none exists), and a method to add numbers into the structure.

Key Insights

  • Use a queue to maintain the order of potential unique numbers.
  • Use a hash table (or map) to count the occurrences of each number.
  • When showing the first unique number, remove numbers from the front of the queue if their frequency is more than one.
  • All operations (add and showFirstUnique) can be done in O(1) amortized time.

Space and Time Complexity

Time Complexity: O(1) amortized for each add and showFirstUnique call. Space Complexity: O(n), where n is the number of distinct integers encountered.

Solution

We design the FirstUnique class using two main data structures: a queue and a hash map (or dictionary). The queue preserves the order of insertion for unique candidates, while the hash map holds the frequency count for each integer.

When a new number is added:

  • Increment its count in the hash map.
  • If the count is one, append it to the queue.

To retrieve the first unique number:

  • While the queue is not empty and the count for the element at the front is greater than one, remove it from the queue.
  • Return the front element of the queue if it exists, otherwise return -1.

This approach ensures that we are always up-to-date with the current first unique number.

Code Solutions

import collections

class FirstUnique:
    # Initialize the object with the numbers in the queue.
    def __init__(self, nums):
        # Using deque for efficient popleft operations.
        self.queue = collections.deque()
        # Dictionary to store frequency count.
        self.count = collections.defaultdict(int)
        # Process the initial list of numbers.
        for num in nums:
            self.add(num)
    
    # Returns the value of the first unique integer of the queue.
    def showFirstUnique(self):
        # Remove numbers from the front if they are no longer unique.
        while self.queue and self.count[self.queue[0]] > 1:
            self.queue.popleft()
        # Return the first unique number if available.
        return self.queue[0] if self.queue else -1
    
    # Inserts value to the queue.
    def add(self, value):
        self.count[value] += 1
        # If it is the first occurrence, append it to the queue.
        if self.count[value] == 1:
            self.queue.append(value)
← Back to All Questions