✅✅ Two Approaches || Ordered Set || Priority Queue (Min-Heap) || Easy Codes
1. Approach 1 (Ordered Set)IntuitionThe problem requires efficiently managing and querying indices associated with numbers. We use two hash maps:
mp to track th
# 1. Approach 1 (Ordered Set)
# Intuition
The problem requires efficiently managing and querying indices associated with numbers. We use two hash maps:  
- `mp` to track the number at each index.  
- `setMp` to maintain a sorted set of indices for each number.  
Using `set<int>`, we ensure fast access to the smallest index for a given number.

# Approach
1. **Data Structures**  
   - `unordered_map<int, int> mp`: Stores `{index -> number}`.  
   - `unordered_map<int, set<int>> setMp`: Stores `{number -> sorted set of indices}`.  

2. **change(index, number)**  
   - If `index` already has a number, remove it from `setMp[prevNum]`.  
   - If `setMp[prevNum]` becomes empty, erase it from `setMp`.  
   - Assign `number` to `index` and insert `index` into `setMp[number]`.  

3. **find(number)**  
   - Return the smallest index in `setMp[number]` if it exists; otherwise, return `-1`.  

# Complexity Analysis
- **change(index, number)**:  
  - Insertion and deletion in `unordered_map` are **O(1)** on average.  
  - Operations on `set<int>` (insertion, deletion) are **O(log k)**, where `k` is the number of indices for a number.  
  - **Overall: O(log k)**.  

- **find(number)**:  
  - Accessing `setMp[number].begin()` is **O(1)**, but checking for an empty set is needed.  
  - **Overall: O(1)**.  

# Space Complexity
- `mp` stores `O(n)` entries.  
- `setMp` stores `O(n)` indices across different sets.  
- **Overall: O(n)**.  

# Code 1 -> Ordered Set
```cpp []
class NumberContainers {
public:
    unordered_map<int,int>mp;
    unordered_map<int,set<int>>setMp;
    NumberContainers() {
    }
    void change(int index, int number) {
        if(mp[index]){
            int prevNum=mp[index];
            setMp[prevNum].erase(index);
            if(setMp[prevNum].empty()){
                setMp.erase(prevNum);
            }
        }
        mp[index]=number;
        setMp[number].insert(index);
    }
    int find(int number) {
        return *setMp[number].begin()?*setMp[number].begin():-1;
    }
};
```

---

---
# 2. Approach 2 (Using Priority Queue (Min-Heap))
# Intuition
We need to efficiently store and query indices associated with numbers. Instead of using `set<int>`, we use a **min-heap (priority queue)** to keep track of the smallest index efficiently.  
- A **hash map (`idxToNum`)** stores the mapping of indices to numbers.  
- A **min-heap (`numToIdx`)** maintains indices sorted for each number, allowing efficient retrieval of the smallest index.

# Approach
1. **Data Structures**  
   - `unordered_map<int, int> idxToNum`: Stores `{index -> number}`.  
   - `unordered_map<int, priority_queue<int, vector<int>, greater<int>>> numToIdx`: Stores `{number -> min-heap of indices}`.  

2. **change(index, number)**  
   - Update `idxToNum[index]` with `number`.  
   - Push `index` into `numToIdx[number]`.  

3. **find(number)**  
   - If `numToIdx[number]` doesn't exist, return `-1`.  
   - Otherwise, retrieve the smallest index from the min-heap.  
   - If the index at the top of the heap has a different number (stale entry), remove it and continue checking.  
   - Return the first valid index or `-1` if none are found.  

# Complexity Analysis
- **change(index, number)**:  
  - Insertion in `unordered_map` is **O(1)**.  
  - Pushing into a **min-heap** is **O(log k)**, where `k` is the number of indices for `number`.  
  - **Overall: O(log k)**.  

- **find(number)**:  
  - Accessing the top of the min-heap is **O(1)**.  
  - Removing stale indices may take **O(log k)** in the worst case.  
  - **Overall: O(log k)**.  

# Space Complexity
- `idxToNum` stores **O(n)** entries.  
- `numToIdx` stores indices in heaps, leading to **O(n)** storage.  
- **Overall: O(n)**.  

# Code 2
```cpp []
class NumberContainers {
public:
    unordered_map<int,int>idxToNum;
    unordered_map<int,priority_queue<int,vector<int>,greater<int>>>numToIdx;

    NumberContainers() { 
    }
    
    void change(int index, int number) {
        idxToNum[index] = number;
        numToIdx[number].push(index);
    }
    
    int find(int number) {
        if(!numToIdx.count(number)){
            return -1;
        }
        auto &pq=numToIdx[number];
        while(!pq.empty()){
            int idx=pq.top();
            if(idxToNum[idx]==number) return idx;
            pq.pop();
        }
        return -1;
    }
};
```
# Have a Good Day 😊 UpVote?
['Hash Table', 'Design', 'Heap (Priority Queue)', 'Ordered Set', 'C++']