# 1429. First Unique Number

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fie9b8cakwdKcHlyXbxjw%2Fimage.png?alt=media\&token=4be9af28-d825-4b2b-a841-c229bb12d26e)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2F3xv0zDiQFC7UsE65MJlH%2Fimage.png?alt=media\&token=10946d1b-ce19-4e44-a420-21be6040358a)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2FPEhL3kf8ju6ItDe6ZqDc%2Fimage.png?alt=media\&token=25ee9400-f9ea-4d1a-9883-6b8cbbabb7f4)

time: showFirstUnique: O(1), add(1)

space: O(n)

```java
/*
DoubleLinkedList maintain a unique number list
HashMap record num is in DoubleLinkedList?
set Duplicate check is this number has appeared?
*/

class FirstUnique {
    
    class DoubleLinkedListNode {
        int val;
        DoubleLinkedListNode prev, next;
        DoubleLinkedListNode(int val) {
            this.val = val;
            this.prev = null;
            this.next = null;
        }
    }
    
    private DoubleLinkedListNode head;
    private DoubleLinkedListNode tail;
    private Map<Integer, DoubleLinkedListNode> numToNode;
    private Set<Integer> duplicates;

    public FirstUnique(int[] nums) {
        numToNode = new HashMap<>();
        duplicates = new HashSet<>();
        head = new DoubleLinkedListNode(0); // dummy node
        tail = head;
        for (int num : nums) {
            add(num);
        }
    }
    
    public int showFirstUnique() {
        if (head.next != null) {
            return head.next.val;
        }
        return -1;
    }
    
    public void add(int value) {
        if (duplicates.contains(value)) {
            return;
        }
        if (numToNode.containsKey(value)) {
            remove(value);
            duplicates.add(value);
        } else {
            DoubleLinkedListNode node = new DoubleLinkedListNode(value);
            numToNode.put(value, node);
            tail.next = node;
            node.prev = tail;
            tail = node;
        }
            
    }
    public void remove(int value) {
        DoubleLinkedListNode node = numToNode.get(value);
        DoubleLinkedListNode prev = node.prev;
        prev.next = node.next;
        if (node.next != null) {
            node.next.prev = prev;
        } else {
            tail = prev;
        }
        numToNode.remove(value);
    } 
}

/**
 * Your FirstUnique object will be instantiated and called as such:
 * FirstUnique obj = new FirstUnique(nums);
 * int param_1 = obj.showFirstUnique();
 * obj.add(value);
 */
```