3 Dictionaries | Python O(n * logn)
Note: In C++ or Java, we can use Sorted HashMap, but here in Python, I didn\'t have such option, so I used a heap and Counter to achieve that. (Will create a de
Note: In C++ or Java, we can use Sorted HashMap, but here in Python, I didn\'t have such option, so I used a heap and Counter to achieve that. (Will create a detailed article on how to do that saperately).\n\nSo here, I have to consider 2 maps:\n1. For storing each index-value pair (number against each index)\n2. For storing all indices of a value (heap against each value, to get the minimum index for O(logn))\n\n```\nfrom collections import defaultdict, Counter\nimport heapq\n\nclass NumberContainers:\n\n    def __init__(self):\n        self.elementIndices = defaultdict(list)\n        self.indexToElement = {}\n        self.indicesRemoved = defaultdict(Counter)\n\n    def change(self, index: int, number: int) -> None:\n        # element already exists on this index\n        if index in self.indexToElement and self.indexToElement[index] == number:\n            return\n        \n        # if some other element exists at the index, mark it to remove\n        if index in self.indexToElement:\n            prevVal = self.indexToElement[index]\n            self.indicesRemoved[prevVal][index] += 1\n        \n        self.indexToElement[index] = number\n        heapq.heappush(self.elementIndices[number], index)\n            \n\n    def find(self, number: int) -> int:\n        ## if the element exists in array\n        if self.elementIndices[number]:\n            mn = self.elementIndices[number][0]\n            while self.indicesRemoved[number][mn] and self.elementIndices[number]:\n                self.indicesRemoved[number][mn] -= 1\n                heapq.heappop(self.elementIndices[number])\n                if not self.elementIndices[number]:\n                    break\n                mn = self.elementIndices[number][0]\n            if self.elementIndices[number]:\n                return mn\n        return -1\n\n\n```
['Heap (Priority Queue)', 'Python']