Java TreeSet (super simple)
Intuition\nKeep a TreeSet of all the numbers (videos) NOT uploaded yet.\nYou can then look at the lowest not uploaded value, and the prefix is the value just be
# Intuition\nKeep a TreeSet of all the numbers (videos) NOT uploaded yet.\nYou can then look at the lowest not uploaded value, and the prefix is the value just before this one.\nSince it\'s a tree, it allows to get the lowest value (leftmost node in the tree) in O(log n)\n\n# Complexity\n- Time complexity:\n    - initialization (`new LUPrefix()`) : O(n log n)\n    - upload : O(log n)\n    - longest : O(log n)\n- Space complexity: O(n)\n\n# Code\n```\nclass LUPrefix {\n    \n    TreeSet<Integer> tree = new TreeSet<>();\n    int n;\n\n    public LUPrefix(int n) {\n        for (int i = 1; i <= n ; i++) {\n            tree.add(i);\n        }\n        this.n = n;\n    }\n\n    public void upload(int video) {\n        tree.remove(video);\n    }\n\n    public int longest() {\n        return tree.isEmpty() ? n : tree.first() -1;\n    }\n}\n```\n\n# Note 1\n\nUsing a priority queue (heap) would have had better complexity (O(n) initialization,  O(log n) upload and  O(1) longuest) but in Java implementation, removing from a priority queue is O(n) instead of O(log n).\n\n# Note 2\nThis not the optimal solution, the optimal one is the HashSet/array one. However one advantage of the tree solution, is that the worst case of any `upload()` call is `O(log n)` while for the HashSet/array the worst case of one call is `O(n)` (but `O(1)` amortized).
['Java']