🚀  Min-Heap + Hash Map  | Beats 97.31 %
IntuitionWe need a way to efficiently map indices to numbers and quickly retrieve the smallest index for a given number.
A hash map + min-heap approach works we
![image.png](https://assets.leetcode.com/users/images/9f45ffc1-0208-41ad-b38b-7f2fb575b7d5_1739046529.3134434.png)


# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
We need a way to efficiently map indices to numbers and quickly retrieve the smallest index for a given number.  
A **hash map + min-heap** approach works well for this:  

1. **Hash Map (`indexToElemMap`)** → Stores the number assigned to each index.  
2. **Min-Heap (`priority_queue`) inside a Hash Map (`elemToIndexMap`)** → Keeps track of all indices for a given number, ensuring the smallest one is accessible efficiently.  

# Approach
<!-- Describe your approach to solving the problem. -->
- **`change(index, number)`**:  
  - Store `number` at `index` in `indexToElemMap`.  
  - Push `index` into `elemToIndexMap[number]` (min-heap).  

- **`find(number)`**:  
  - If `number` is not in `elemToIndexMap`, return `-1`.  
  - Pop elements from the heap until the top index is valid (i.e., it still maps to `number` in `indexToElemMap`).  
  - If no valid index remains, return `-1`, otherwise return the smallest valid index.  

# Complexity
- **Time complexity:**
  - `change()` → $$O(\log N)$$ (heap insertion)
  - `find()` → **Amortized** $$O(\log N)$$ (heap cleanup)
  - **Total Complexity:** $$O(Q \log N)$$ for **Q** operations  

- **Space complexity:**
  - $$O(N)$$ for storing indices and numbers  

# Code
```cpp
class NumberContainers {
public:
    // Priority queue to store indices for each number in ascending order.
    // We use a min-heap to easily retrieve the smallest index.
    typedef priority_queue<int, vector<int>, greater<int>> pq;

    // Map that stores a priority queue for each number, where each priority queue stores its indices.
    unordered_map<int, pq> elemToIndexMap;  // Example: {10: {1, 3, 5}}
    
    // Map to store the number associated with each index.
    unordered_map<int, int> indexToElemMap;  // Example: {0: 5}

    NumberContainers() {}

    void change(int index, int number) {
        // Store the number at the given index
        indexToElemMap[index] = number;
        
        // Add the index to the priority queue of the corresponding number
        elemToIndexMap[number].push(index);
    }

    int find(int number) {
        // If the number is not found in the map, return -1
        if (!elemToIndexMap.count(number))
            return -1;

        // We need to make sure the top of the priority queue contains a valid index
        // (one that actually maps to the given number and was not replaced in the past).
        while (!elemToIndexMap[number].empty() && indexToElemMap[elemToIndexMap[number].top()] != number) {
            // Pop invalid indices from the priority queue
            elemToIndexMap[number].pop();
        }

        // (no valid index is left).
        if (elemToIndexMap[number].empty())
            return -1;

        // If there's a valid index left, return the smallest index (top of the priority queue)
        return elemToIndexMap[number].top();
    }
};

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers* obj = new NumberContainers();
 * obj->change(index, number);  // This changes the number at the given index.
 * int param_2 = obj->find(number);  // This finds the smallest index associated with the given number.
 */

['Hash Table', 'Heap (Priority Queue)', 'C++']