hashmaps||C++97.19%|Py3 99.51%
IntuitionDone long ago.
Use std::unordered_map to solve with 91ms Beats 90.63%
std::set is an ordered set which is implemented by the red-black tree
2nd approac
# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
Done long ago.
Use `std::unordered_map` to solve with 91ms Beats 90.63%
`std::set` is an ordered set which is implemented by the red-black tree
2nd approach uses `priority_queue` for the values `idx` which is faster.
3rd approach uses C++ `pop_heap & push_heap` which is similar to Python's solution using `heappush, heappop`.
# Approach
<!-- Describe your approach to solving the problem. -->
1. Construct 2 maps, `unordered_map<int, int> mp`, `unordered_map<int, set<int>> idx`. 
2. the values for `idx` are `set<int>` which is a red-black tree with accessing time $O(\log n)$
3. The constructor `reserves` the space for `1e5` which can avoid of rehashing & speeds up for later performing methods
4. the method `void change(int index, int number)` set `mp[x]=number, idx[number].insert(index)` & erase the old values. That takes $O(\log n)$ time
5. the `find` method will return the minimal element if idx has number  otherwise -1. This method takes $O(1)$ time accessing `begin()`
6.  `priority_queue` is faster than `set`. The 2nd C++ code is implemented using `priority_queue` for the values `idx` to replace `set<int>`. Even the method `find` has much more TC,say $O(k\log n)$ where $k\leq n$, it's faster.
7. 3rd approach is reimplementing 2nd C++ using `push_heap` & `pop_heap` which has almost the same structure like Python's code. 
8. Python code is the the fastest one among all.

# Code||C++ 91ms Beats 90.63%
```cpp []
class NumberContainers {
public:
    unordered_map<int, int> mp;
    unordered_map<int, set<int>> idx;
    NumberContainers() {
        mp.reserve(100000);
    }
    
    void change(int index, int number) {
        if (mp.count(index)){
            int x=mp[index];
            idx[x].erase(index); 
            if (idx[x].size()==0) idx.erase(x);
        }
        mp[index]=number;
        idx[number].insert(index);
    }
    
    int find(int number) {
        if (idx.count(number)==0) 
            return -1;
        return *(idx[number].begin());
    }
};

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index,number);
 * int param_2 = obj->find(number);
 */
```
# C++ using minHeap for idx||85 ms Beats 94.69%|| find using pq called by ref 74ms beats 97.19%
```cpp [C++]
class NumberContainers {
public:
    unordered_map<int, int> mp;
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> idx;
    NumberContainers() {
        mp.reserve(100000);
    }
    
    void change(int index, int number) {
        mp[index]=number;
        idx[number].push(index);
    }
    
    int find(int number) {
        if (idx.count(number)==0) 
            return -1;
        while(!idx[number].empty()){
            int i=idx[number].top();
            if (mp[i]==number) return i;
            idx[number].pop();
        }
        return -1;
    }
};

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
```
```cpp [find with ref pq]
int find(int number) {
        if (idx.count(number)==0) 
            return -1;
        auto& pq=idx[number];// by reference
        while(!pq.empty()){
            int i=pq.top();
            if (mp[i]==number) return i;
            pq.pop();
        }
        return -1;
    }
```
# LC's similar design problems
These similar design problems need 2 tables.
[2353. Design a Food Rating System](https://leetcode.com/problems/design-a-food-rating-system/solutions/4414591/2c-2-tables-set-vs-priority-queue-267ms-beats-100/)
[1845. Seat Reservation Manager](https://leetcode.com/problems/seat-reservation-manager/solutions/4254433/c-priority-queue-vs-set-vs-bool-array-214ms-beats-100/)
[https://youtu.be/QznanPtol58?si=WiltWBoiA3OGpL46](https://youtu.be/QznanPtol58?si=WiltWBoiA3OGpL46)
# Code using push_heap, pop_heap||C++ 88ms|Python3 71ms Beats 99.51%
```C++ []
class NumberContainers {
public:
    unordered_map<int, int> mp;
    unordered_map<int, vector<int>> idx;
    NumberContainers() {
        mp.reserve(100000);
    }
    
    void change(int index, int number) {
    //    if (mp.count(index) && mp[index]==number) return;
        mp[index]=number;
        auto& I=idx[number];
        I.push_back(index);
        push_heap(I.begin(), I.end(), greater<>());
    }
    
    int find(int number) {
        auto it=idx.find(number);
        if (it==idx.end()) 
            return -1;
        auto& I=it->second;
        while(!I.empty()){
            pop_heap(I.begin(), I.end(), greater<>());
            int i=I.back();
            if (mp[i]==number){
                push_heap(I.begin(), I.end(), greater<>());
                return i;
            }
            I.pop_back();
        }
        return -1;
    }
};

auto init = []()
{ 
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 'c';
}();
```
```Python []
class NumberContainers:

    def __init__(self):
        self.mp={}
        self.idx=defaultdict(list)

    def change(self, index: int, number: int) -> None:
        self.mp[index]=number
        heappush(self.idx[number], index)
        

    def find(self, number: int) -> int:
        if number not in self.idx:
            return -1
        while self.idx[number]:
            i=self.idx[number][0]
            if self.mp[i]==number: return i
            heappop(self.idx[number])
        return -1



# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
```

['Hash Table', 'Design', 'Heap (Priority Queue)', 'Ordered Set', 'C++', 'Python3']