Easy & Detailed Approch ✅ || HashMap 🔥 || Ordered Set 🔥 || Cpp | Java | Python | Js
Intuition
We need a data structure to efficiently update and find the smallest index for a given number.
A hash map (unordered_map<int, int> mp) can store index
# **Intuition**
<!-- Describe your first thoughts on how to solve this problem. -->
- We need a data structure to efficiently **update** and **find** the smallest index for a given number.
- A **hash map** (`unordered_map<int, int> mp`) can store index-to-number mapping for fast updates.
- A **sorted map of sets** (`map<int, set<int>> pos`) helps in retrieving the smallest index of a number.

---

# **Approach**
<!-- Describe your approach to solving the problem. -->
1. **`change(index, number)` Operation:**
   - If `index` already exists in `mp`, remove it from its previous number’s set.
   - Assign `number` to `index` in `mp`.
   - Insert `index` into the set corresponding to `number` in `pos`.

2. **`find(number)` Operation:**
   - If `number` exists in `pos`, return the **smallest index** (first element of the set).
   - Otherwise, return `-1`.

---

# **Complexity Analysis**
- **Time Complexity:**
  - `change(index, number)`: **O(log n)** due to insertions/removals from `map<int, set<int>>`.
  - `find(number)`: **O(1)** as we fetch the smallest index using `set.begin()`.

- **Space Complexity:**
  - **O(n)** where `n` is the number of indices stored in `mp` and `pos`.


# Code
```cpp []
class NumberContainers {
public:
    unordered_map<int, int> mp;  // Stores the mapping of index → number
    map<int, set<int>> pos;      // Stores the mapping of number → sorted set of indices

    NumberContainers() {}

    // Updates the number at a given index
    void change(int index, int number) {
        // Step 1: If the index already exists in `mp`, remove it from its previous number group
        if (mp.find(index) != mp.end()) { 
            int old = mp[index];  // Get the old number at this index

            // Remove this index from the set of indices where the old number was stored
            pos[old].erase(index);  

            // If there are no indices left for this old number, remove it from the `pos` map
            if (pos[old].empty()) {
                pos.erase(old);  
            }
        }
        
        // Step 2: Update the index with the new number
        mp[index] = number;  

        // Step 3: Add this index to the set of indices for the new number
        pos[number].insert(index); 
    }

    // Returns the smallest index where the given number is stored
    int find(int number) {
        // If the number is not present in `pos` or has no indices left, return -1
        if (pos.find(number) == pos.end() || pos[number].empty()) {
            return -1;
        }

        // The `set<int>` automatically keeps indices sorted,
        // so we return the smallest index (first element in the set)
        return *pos[number].begin();  
    }
};


```
```javascript []
class NumberContainers {
    constructor() {
        this.mp = new Map(); // Stores index → number mapping
        this.pos = new Map(); // Stores number → sorted set of indices
    }

    // Updates the number at a given index
    change(index, number) {
        if (this.mp.has(index)) {
            let oldNumber = this.mp.get(index); // Get the old number at this index

            // Remove index from old number's set
            this.pos.get(oldNumber).delete(index);

            // If the set becomes empty, remove the number entry
            if (this.pos.get(oldNumber).size === 0) {
                this.pos.delete(oldNumber);
            }
        }

        // Update index with new number
        this.mp.set(index, number);

        // Add index to the new number's set
        if (!this.pos.has(number)) {
            this.pos.set(number, new Set());
        }
        this.pos.get(number).add(index);
    }

    // Returns the smallest index where the number is stored
    find(number) {
        if (!this.pos.has(number) || this.pos.get(number).size === 0) {
            return -1;
        }

        // Convert Set to an array and return the smallest index
        return Math.min(...this.pos.get(number));
    }
}

```
```python []
from sortedcontainers import SortedSet

class NumberContainers:
    def __init__(self):
        self.mp = {}  # Stores index → number mapping
        self.pos = {}  # Stores number → sorted set of indices

    # Updates the number at a given index
    def change(self, index: int, number: int) -> None:
        if index in self.mp:
            old_number = self.mp[index]  # Get the old number at this index

            # Remove index from the set of old number
            self.pos[old_number].discard(index)

            # If the set becomes empty, remove the number entry
            if not self.pos[old_number]:
                del self.pos[old_number]

        # Update index with new number
        self.mp[index] = number

        # Add index to the new number's set
        if number not in self.pos:
            self.pos[number] = SortedSet()
        self.pos[number].add(index)

    # Returns the smallest index where the number is stored
    def find(self, number: int) -> int:
        if number not in self.pos or not self.pos[number]:
            return -1
        return self.pos[number][0]  # Get the smallest index

```
```java []
import java.util.*;

class NumberContainers {
    private Map<Integer, Integer> mp; // Stores index → number mapping
    private TreeMap<Integer, TreeSet<Integer>> pos; // Stores number → sorted set of indices

    public NumberContainers() {
        mp = new HashMap<>();
        pos = new TreeMap<>();
    }

    // Updates the number at a given index
    public void change(int index, int number) {
        if (mp.containsKey(index)) {
            int oldNumber = mp.get(index); // Get the old number at this index

            // Remove index from the set of old number
            pos.get(oldNumber).remove(index);

            // If the set becomes empty, remove the number entry
            if (pos.get(oldNumber).isEmpty()) {
                pos.remove(oldNumber);
            }
        }

        // Update index with new number
        mp.put(index, number);

        // Add index to the new number's set
        pos.putIfAbsent(number, new TreeSet<>());
        pos.get(number).add(index);
    }

    // Returns the smallest index where the number is stored
    public int find(int number) {
        if (!pos.containsKey(number) || pos.get(number).isEmpty()) {
            return -1;
        }
        return pos.get(number).first(); // Get the smallest index
    }
}

```

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