HashMap | PriorityQueue | Lazy Deletion | Example Walkthrough
Intuition 🔍
💡 Use a mapping from index to number.
🚀 For each number, maintain a min-heap of indices.
🔄 On update, insert the new index without removing the old
# Intuition 🔍  
- 💡 Use a mapping from index to number.  
- 🚀 For each number, maintain a min-heap of indices.  
- 🔄 On update, insert the new index without removing the old one (lazy deletion).  
- ⚡ When querying, pop invalid indices until the top is valid.  
- ⏱️ Efficient operations with $$O(\log n)$$ updates and queries.

# Example 📊  
| **Operation**        | **Mapping (m)**                 | **Heap for 10**                      | **Heap for 20**  | **Output** |
|----------------------|---------------------------------|--------------------------------------|------------------|------------|
| 🔍 **find(10)**      | {}                              | {}                                   | {}               | **-1**     |
| ✏️ **change(2,10)**  | {2:10}                          | [2]                                  | {}               |            |
| ✏️ **change(1,10)**  | {2:10, 1:10}                    | [1, 2]                               | {}               |            |
| ✏️ **change(3,10)**  | {2:10, 1:10, 3:10}              | [1, 2, 3]                            | {}               |            |
| ✏️ **change(5,10)**  | {2:10, 1:10, 3:10, 5:10}         | [1, 2, 3, 5]                         | {}               |            |
| 🔍 **find(10)**      | {2:10, 1:10, 3:10, 5:10}         | [1, 2, 3, 5] → **smallest=1**         | {}               | **1**      |
| ✏️ **change(1,20)**  | {2:10, 1:20, 3:10, 5:10}         | [1, 2, 3, 5] *(1 invalid)*           | [1]              |            |
| 🔍 **find(10)**      | {2:10, 1:20, 3:10, 5:10}         | [2, 3, 5] → **smallest=2**            | [1]              | **2**      |

# Complexity ⚙️  
- **Time complexity:**  
                - change: $$O(\log n)$$, 
                - find: $$O(\log n)$$ amortized  
- **Space complexity:**  $$O(n)$$

# Code

```cpp []
class NumberContainers {
    unordered_map<int,int> m;
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> d;
public:
    NumberContainers(){}
    void change(int i, int n) {
        if(m.count(i) && m[i]==n)return;
        m[i]=n;
        d[n].push(i);
    }
    int find(int n) {
        if(!d.count(n)) return -1;
        auto &pq = d[n];
        while(!pq.empty() && m[pq.top()]!=n) pq.pop();
        return pq.empty()? -1 : pq.top();
    }
};
```

```java []
class NumberContainers {
    Map<Integer,Integer> m;
    Map<Integer,PriorityQueue<Integer>> d;
    public NumberContainers() {
        m = new HashMap<>();
        d = new HashMap<>();
    }
    public void change(int i, int n) {
        if(m.containsKey(i) && m.get(i)==n)return;
        m.put(i,n);
        d.computeIfAbsent(n,k->new PriorityQueue<>()).offer(i);
    }
    public int find(int n) {
        if(!d.containsKey(n)) return -1;
        PriorityQueue<Integer> pq = d.get(n);
        while(!pq.isEmpty() && m.get(pq.peek())!=n) pq.poll();
        return pq.isEmpty()? -1 : pq.peek();
    }
}
```

```python []
import heapq
class NumberContainers:
    def __init__(self):
        self.m = {}
        self.d = {}
    def change(self, i, n):
        if i in self.m and self.m[i]==n: return
        self.m[i] = n
        self.d.setdefault(n, [])
        heapq.heappush(self.d[n], i)
    def find(self, n):
        if n not in self.d: return -1
        while self.d[n] and self.m.get(self.d[n][0])!=n:
            heapq.heappop(self.d[n])
        return self.d[n][0] if self.d[n] else -1
```

```javascript []
var NumberContainers = function() {
    this.m = new Map();
    this.d = new Map();
};
NumberContainers.prototype.change = function(i, n) {
    if(this.m.has(i) && this.m.get(i)==n)return;
    this.m.set(i, n);
    if(!this.d.has(n)) this.d.set(n, new MinHeap());
    this.d.get(n).push(i);
};
NumberContainers.prototype.find = function(n) {
    if(!this.d.has(n)) return -1;
    let h = this.d.get(n);
    while(h.size() && this.m.get(h.peek())!==n) h.pop();
    return h.size()? h.peek() : -1;
};
function MinHeap() {
    this.a = [];
}
MinHeap.prototype.push = function(x) {
    this.a.push(x);
    let i = this.a.length - 1;
    while(i>0){
        let p = (i-1)>>1;
        if(this.a[p] <= this.a[i]) break;
        [this.a[p], this.a[i]] = [this.a[i], this.a[p]];
        i = p;
    }
};
MinHeap.prototype.pop = function() {
    let r = this.a[0], l = this.a.pop();
    if(this.a.length){
        this.a[0] = l;
        let i = 0, n = this.a.length;
        while(true){
            let l = i*2+1, r = i*2+2, m = i;
            if(l < n && this.a[l] < this.a[m]) m = l;
            if(r < n && this.a[r] < this.a[m]) m = r;
            if(m === i) break;
            [this.a[i], this.a[m]] = [this.a[m], this.a[i]];
            i = m;
        }
    }
    return r;
};
MinHeap.prototype.peek = function() {
    return this.a[0];
};
MinHeap.prototype.size = function() {
    return this.a.length;
};
```
['Python', 'C++', 'Java', 'JavaScript']