Lintcode 685. First Unique Number in Data Stream

Given a continuous stream of numbers, write a function that returns the first unique number whenever terminating number is reached(include terminating number). If there no unique number before terminating number or you can't find this terminating number, return -1.

Example

Example1

Input: 
[1, 2, 2, 1, 3, 4, 4, 5, 6]
5
Output: 3

Example2

Input: 
[1, 2, 2, 1, 3, 4, 4, 5, 6]
7
Output: -1

Solution:
HashMap + Linked list

Code (Java):

public class Solution {
    /**
     * @param nums: a continuous stream of numbers
     * @param number: a number
     * @return: returns the first unique number
     */
    public int firstUniqueNumber(int[] nums, int number) {
        // Write your code here
        if (nums == null || nums.length == 0) {
            return -1;
        }

        MyLinkedList canidateList = new MyLinkedList();
        Map<Integer, ListNode> numToNodeMap = new HashMap<>();
        for (int num : nums) {
            insert(num, canidateList, numToNodeMap);
            if (num == number) {
                if (canidateList.isEmpty()) {
                    return -1;
                } else {
                    return canidateList.getFirst().val;
                }
            }
        }

        return -1;
    }

    private void insert(int num, MyLinkedList list, Map<Integer, ListNode> map) {
        if (map.containsKey(num)) {
            // need to distiguish the 2nd time or 2+ times
            if (map.get(num) != null) {
                list.remove(map.get(num));
                map.put(num, null);
            }
        } else {
            ListNode node = list.append(num);
            map.put(num, node);
        }
    }
}

class ListNode {
    ListNode next, prev;
    int val;
    public ListNode(int val) {
        this.val = val;
        next = prev = null;
    }
}

class MyLinkedList {
    private ListNode dummyHead;
    private ListNode dummyTail;
    public MyLinkedList() {
        dummyHead = new ListNode(-1);
        dummyTail = new ListNode(-1);

        dummyHead.next = dummyTail;
        dummyTail.prev = dummyHead;
    }

    public ListNode getFirst() {
        return dummyHead.next;
    }

    public boolean isEmpty() {
        return dummyHead.next == dummyTail;
    }

    public void remove(ListNode node) {
        ListNode prevNode = node.prev;
        ListNode nextNode = node.next;
        prevNode.next = nextNode;
        nextNode.prev = prevNode;
    }

    public ListNode append(int num) {
        ListNode currNode = new ListNode(num);
        ListNode prevNode = dummyTail.prev;
        prevNode.next = currNode;
        currNode.next = dummyTail;
        dummyTail.prev = currNode;
        currNode.prev = prevNode;

        return currNode;
    }
}