[Java/Python 3] TreeSet/SortedList w/ brief explanation and analysis.
Q & A\n\nQ1: How many third party packages are pre installed on leetcode server? And where to get such list?\nA1: Please see What are the environments for the p
**Q & A**\n\nQ1: How many third party packages are pre installed on leetcode server? And where to get such list?\nA1: Please see [What are the environments for the programming languages?](https://support.leetcode.com/hc/en-us/articles/360011833974-What-are-the-environments-for-the-programming-languages-).\n\nQ2: Why `find` is `O(logn)` since the values are sorted?\nA2:  \n\n\n1)  In Python 3 code `SortedList[i]` is actually `SortedList.__getitem__`, which cost time `O(logn)`. Please refer to [source code](https://grantjenks.com/docs/sortedcontainers/_modules/sortedcontainers/sortedlist.html#SortedList.__getitem__) for more details.\n2)  In Java code, the `TreeSet` is implemented based on `TreeMap`, which is implemented using Red-Black Tree. [Red-Black Tree](https://en.m.wikipedia.org/wiki/Red%E2%80%93black_tree)  is a self-balancing binary search tree, and any search operation cost `O(logn)`. Hence the `TreeSet.first()` cost `O(logn)`.\n\n\n**End of Q & A**\n\n----\n\nSince the problem request that the smallest index of a given `number` be returned, a `TreeSet/SortedList` is a reasonable choice.\n\nTherefore, we can use `2` `HashMap/dict` to store `number/indices` and `index/number` bindings respectively.\n\nNote: For each call of `change`, we first check if there has already been a `number` filled at the `index`: if yes, discard the old value at the `index` first, then update/insert the new value.\n\n```java\n    private Map<Integer, TreeSet<Integer>> numToIndices = new HashMap<>();\n    private Map<Integer, Integer> indexToNum = new HashMap<>();\n\n    public NumberContainers() {}\n    \n    public void change(int index, int number) {\n        if (indexToNum.containsKey(index)) {\n            int old = indexToNum.get(index);\n            numToIndices.get(old).remove(index);\n            if (numToIndices.get(old).isEmpty()) {\n                numToIndices.remove(old);\n            }\n        }\n        indexToNum.put(index, number);\n        numToIndices.computeIfAbsent(number, s -> new TreeSet<>()).add(index);\n    }\n    \n    public int find(int number) {\n        if (numToIndices.containsKey(number)) {\n            return numToIndices.get(number).first();\n        }\n        return -1;\n    }\n```\n```python\nfrom sortedcontainers import SortedList\n\nclass NumberContainers:\n\n    def __init__(self):\n        self.num_to_indices = defaultdict(SortedList)\n        self.index_to_num = {}\n\n    def change(self, index: int, number: int) -> None:\n        if index in self.index_to_num:\n            old = self.index_to_num[index]\n            self.num_to_indices[old].discard(index)\n            if not self.num_to_indices[old]:\n                del self.num_to_indices[old]\n        self.num_to_indices[number].add(index)\n        self.index_to_num[index] = number\n            \n\n    def find(self, number: int) -> int:\n        if number in self.num_to_indices:\n            return self.num_to_indices[number][0]\n        return -1\n```\n\n**Analysis:**\n\nOverall space: `O(n)`\n\nTime for both `change` and `find`: `O(logn)`, where `n` is the total count of numbers in the container.
['Java', 'Python3']