First Unique Number - Practice Coding Problems

First Unique Number - Problem

Array Hash Table Design Queue Data Stream Medium

You have a queue of integers, and 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) - Inserts value to the queue.

Input & Output

Example 1 — Basic Operations

$ Input: FirstUnique firstUnique = new FirstUnique([2,3,5]); firstUnique.showFirstUnique(); firstUnique.add(5); firstUnique.showFirstUnique();

› Output: 2, 2

💡 Note: Initially first unique is 2. After adding 5 (which already exists), 2 is still the first unique.

Example 2 — Remove First Unique

$ Input: FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); firstUnique.showFirstUnique(); firstUnique.add(7); firstUnique.add(3); firstUnique.showFirstUnique();

› Output: -1, 3

💡 Note: All 7s are duplicates so first call returns -1. After adding 3, it becomes the first unique.

Example 3 — Multiple Unique Elements

$ Input: FirstUnique firstUnique = new FirstUnique([809]); firstUnique.showFirstUnique(); firstUnique.add(809); firstUnique.showFirstUnique();

› Output: 809, -1

💡 Note: Initially 809 is unique. After adding another 809, no unique elements remain.

Constraints

1 ≤ nums.length ≤ 10⁵
1 ≤ nums[i] ≤ 10⁸
1 ≤ value ≤ 10⁸
At most 50000 calls will be made to showFirstUnique and add.

Visualization

Tap to expand

Understanding the Visualization

Input Stream

Numbers arrive in sequence: [2,3,5]

Track Unique

Maintain order of first occurrences

Query Result

Return first element that appears exactly once

Key Takeaway

🎯 Key Insight: Use doubly linked list to maintain unique elements and achieve O(1) queries

Asked in

A Amazon 45 B Bloomberg 32 G Google 28 M Microsoft 25

The key insight is to use a hash map for frequency tracking and a doubly linked list for unique elements. The optimal approach achieves O(1) for all operations by maintaining a linked list of unique elements and removing them immediately when they become duplicates. Time: O(1), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map + Doubly Linked List	O(1)	O(n)	Use hash map for O(1) frequency updates and doubly linked list for O(1) removals
Brute Force	O(n)	O(n)	Check all elements to count frequencies for each operation
Hash Map + Queue	O(n)	O(n)	Use hash map to track frequencies and queue to maintain order

Hash Map + Doubly Linked List — Algorithm Steps

Step 1: Use hash map for frequencies and linked list for unique elements
Step 2: For add: if first time, add to list; if second time, remove from list
Step 3: showFirstUnique returns head of linked list in O(1)

Visualization

Tap to expand

Step-by-Step Walkthrough

Structure

Frequency map + doubly linked list of unique elements

Add Operation

O(1) add to tail or O(1) remove from list

Query

O(1) return head of unique list

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct ListNode {
    int val;
    struct ListNode* prev;
    struct ListNode* next;
} ListNode;

typedef struct {
    int freq[20001];
    ListNode* nodeMap[20001];
    ListNode* head;
    ListNode* tail;
} FirstUnique;

ListNode* createNode(int val) {
    ListNode* node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->prev = NULL;
    node->next = NULL;
    return node;
}

void addToTail(FirstUnique* obj, ListNode* node) {
    ListNode* prevNode = obj->tail->prev;
    prevNode->next = node;
    node->prev = prevNode;
    node->next = obj->tail;
    obj->tail->prev = node;
}

void removeNode(ListNode* node) {
    ListNode* prevNode = node->prev;
    ListNode* nextNode = node->next;
    prevNode->next = nextNode;
    nextNode->prev = prevNode;
}

FirstUnique* firstUniqueCreate(int* nums, int numsSize) {
    FirstUnique* obj = (FirstUnique*)malloc(sizeof(FirstUnique));
    memset(obj->freq, 0, sizeof(obj->freq));
    memset(obj->nodeMap, 0, sizeof(obj->nodeMap));
    obj->head = createNode(0);
    obj->tail = createNode(0);
    obj->head->next = obj->tail;
    obj->tail->prev = obj->head;
    for (int i = 0; i < numsSize; i++) {
        firstUniqueAdd(obj, nums[i]);
    }
    return obj;
}

int firstUniqueShowFirstUnique(FirstUnique* obj) {
    if (obj->head->next == obj->tail) {
        return -1;
    }
    return obj->head->next->val;
}

void firstUniqueAdd(FirstUnique* obj, int value) {
    int idx = value + 10000;
    if (obj->freq[idx] > 0) {
        obj->freq[idx]++;
        if (obj->freq[idx] == 2 && obj->nodeMap[idx] != NULL) {
            removeNode(obj->nodeMap[idx]);
            free(obj->nodeMap[idx]);
            obj->nodeMap[idx] = NULL;
        }
    } else {
        obj->freq[idx] = 1;
        ListNode* newNode = createNode(value);
        addToTail(obj, newNode);
        obj->nodeMap[idx] = newNode;
    }
}

int* solution(int* nums, int numsSize, int* returnSize) {
    FirstUnique* obj = firstUniqueCreate(nums, numsSize);
    int* result = (int*)malloc(3 * sizeof(int));
    result[0] = firstUniqueShowFirstUnique(obj);
    firstUniqueAdd(obj, 2);
    result[1] = firstUniqueShowFirstUnique(obj);
    firstUniqueAdd(obj, 3);
    result[2] = firstUniqueShowFirstUnique(obj);
    *returnSize = 3;
    free(obj->head);
    free(obj->tail);
    free(obj);
    return result;
}

int main() {
    char line[10000];
    fgets(line, sizeof(line), stdin);
    line[strcspn(line, "\n")] = 0;
    
    int nums[1000];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    while (token) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int returnSize;
    int* result = solution(nums, numsSize, &returnSize);
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(1)

showFirstUnique is O(1) as it just returns head of linked list

✓ Linear Growth

Space Complexity

O(n)

Hash map stores frequencies and linked list stores at most n unique elements

⚡ Linearithmic Space

67.5K Views

High Frequency

~35 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map + Doubly Linked List — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler