Python | Min Heap | O(log n) / O(k log n), O(n) | Beats 100%
CodeComplexity

Time complexity: change()=O(logn),find()=O(klogn). Change() adds to heap which takes log n. Find() removes k possible indices from min heap whic
# Code
```python3 []
class NumberContainers:

    def __init__(self):
        self.index_num = {} # index: num at index
        self.num_indices = {} # num: min heap of indices where num has been

    def change(self, index: int, number: int) -> None:
        self.index_num[index] = number # set number for index
        
        if number not in self.num_indices: 
            self.num_indices[number] = [] # make heap if new num
        heapq.heappush(self.num_indices[number], index) # add index to min heap

    def find(self, number: int) -> int:
        if number not in self.num_indices: 
            return -1 # no index with number
            
        pos_indices = self.num_indices[number]
        while pos_indices:
            min_index = pos_indices[0] # check lowest index
            
            if self.index_num[min_index] == number: 
                return min_index # valid index, found num at index

            heapq.heappop(pos_indices) # invalid index, new num at index
        
        return -1 # no valid index found
```

# Complexity
- Time complexity: $$ change()=O(\log n), find()=O(k\log n)$$. Change() adds to heap which takes log n. Find() removes k possible indices from min heap which takes log n, so k * log n.

- Space complexity: $$O(n)$$. Worse case, index_num has a key for each n index and num_indices has min heaps of n indices.

# Performance

![Screenshot (861).png](https://assets.leetcode.com/users/images/39feb4ad-8a29-4133-a343-94d3acf9706c_1738976008.1276875.png)


['Python3']