First Unique Number: priority queue, hash tables and math

Tough problem: https://leetcode.com/problems/first-unique-number/

1429. First Unique Number

Medium

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.

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.

Accepted

39

Submissions

75,747

Here is the approach:
A) Have a priority queue instead of a regular queue
B) The priority should be a combination of the value count and the value order. The value count is more important, the order is used as a tie-breaker. Look at the constraints of the problem and you can come up with a simple formula for the priority
C) In a hash table, store the count of each number
D) The ShowFirstUnique becomes trivial: if the head (via a Peak method) has one occurrence, return it, otherwise -1
E) When adding in the queue, make sure to check whether the element is the first, if so dequeue first

Code is down below, cheers, ACC.

    public class FirstUnique
    {
        private PriorityQueue pQueue = new PriorityQueue("up");
        private Hashtable count = new Hashtable();
        private long order = 0;
        private const long M = 100000001;
        public FirstUnique(int[] nums)
        {
            foreach(int n in nums)
            {
                if (!count.ContainsKey(n)) count.Add(n, 0L);
                count[n] = (long)count[n] + 1;

                if (pQueue.Count > 0 && (int)pQueue.Peak() == n)
                {
                    pQueue.Dequeue();
                }

                order++;
                pQueue.Enqueue(n, (long)count[n] * M + order);
            }
        }

        public int ShowFirstUnique()
        {
            if (pQueue.Count == 0) return -1;
            int peak = (int)pQueue.Peak();

            if ((long)count[peak] == 1) return peak;
            return -1;
        }

        public void Add(int value)
        {
            if (!count.ContainsKey(value)) count.Add(value, 0L);
            count[value] = (long)count[value] + 1;

            if (pQueue.Count > 0 && (int)pQueue.Peak() == value)
            {
                pQueue.Dequeue();
            }

            order++;
            pQueue.Enqueue(value, (long)count[value] * M + order);
        }
    }

    public class PriorityQueue
    {
        public struct HeapEntry
        {
            private object item;
            private long priority;
            public HeapEntry(object item, long priority)
            {
                this.item = item;
                this.priority = priority;
            }
            public object Item
            {
                get
                {
                    return item;
                }
            }
            public long Priority
            {
                get
                {
                    return priority;
                }
            }
        }

        private int direction = 0; //0 - up, 1 - down
        private int count;
        private int capacity;
        public HeapEntry[] heap;

        public int Count
        {
            get
            {
                return this.count;
            }
        }

        public PriorityQueue(string directionStr)
        {
            direction = directionStr.Equals("up") ? 0 : 1;
            capacity = 1000000;
            heap = new HeapEntry[capacity];
        }

        public object Peak()
        {
            return heap[0].Item;
        }

        public object Dequeue()
        {
            object result = heap[0].Item;
            //priority = heap[0].Priority;
            count--;
            trickleDown(0, heap[count]);
            return result;
        }

        public void Enqueue(object item, long priority)
        {
            count++;
            bubbleUp(count - 1, new HeapEntry(item, priority));
        }

        private void bubbleUp(int index, HeapEntry he)
        {
            int parent = (index - 1) / 2;
            // note: (index > 0) means there is a parent
            if (direction == 0)
            {
                while (index > 0 && heap[parent].Priority > he.Priority)
                {
                    heap[index] = heap[parent];
                    index = parent;
                    parent = (index - 1) / 2;
                }
            }
            else
            {
                while (index > 0 && heap[parent].Priority < he.Priority)
                {
                    heap[index] = heap[parent];
                    index = parent;
                    parent = (index - 1) / 2;
                }
            }
            heap[index] = he;
        }

        private void trickleDown(int index, HeapEntry he)
        {
            int child = (index * 2) + 1;
            while (child < count)
            {
                if (direction == 0)
                {
                    if (child + 1 < count && heap[child].Priority > heap[child + 1].Priority)
                    {
                        child++;
                    }
                }
                else
                {
                    if (child + 1 < count && heap[child].Priority < heap[child + 1].Priority)
                    {
                        child++;
                    }
                }
                heap[index] = heap[child];
                index = child;
                child = (index * 2) + 1;
            }
            bubbleUp(index, he);
        }
    }