✔️ Easiest Solution & Beginner Friendly ✔️ | 🔥 HashMap + TreeSet 🔥 | 2 Solutions
IntuitionThe problem requires efficiently updating indices with numbers and quickly retrieving the smallest index associated with a given number. A HashMap is u
# Intuition
The problem requires **efficiently updating indices** with numbers and quickly retrieving the `smallest index` associated with a given number. A `HashMap` is used to store **{index → number}** mappings, allowing **constant-time updates**. To maintain an **ordered list** of `indices` for each number, a `TreeSet` or `Set` inside another `HashMap` is used, ensuring **fast retrieval of the smallest index** in `O(1)` time. When updating an **index**, we remove it from the previous number’s set and insert it into the new number’s set in `O(log n)` time. This approach balances efficient updates and queries, making it suitable for **large constraints**.

# Approach
`Step 1` **Initialize Data Structures**

- Maintain a map `idxToNum` that stores the mapping `{index → number}`
- Maintain a map `numToIdx` that maps `{number → ordered set of indices}` **ordered by index**.

`Step 2:` **Implement change(index, number)**

- If `index` is already present in `idxToNum`, remove its **old** number from `numToIdx`
- Update `idxToNum` with the new `{index → number}`
- Insert `index` into the **ordered set** `numToIdx[number]`

`Step 3` **Implement find(number)**
- If number exists in `numToIdx`, return the **smallest index** from its **ordered set**.
- Otherwise, `return -1`.


# Complexity
- Time complexity : $$O(n)$$
- Space complexity : $$O(n)$$
 
# Code
```Java []
class NumberContainers
{
    private Map<Integer, Integer> idxToNum; // index -> number mapping
    private Map<Integer, TreeSet<Integer>> numToIdx; // number -> sorted index set

    public NumberContainers()
    {
        idxToNum = new HashMap<>();
        numToIdx = new HashMap<>();
    }

    // Step 1: Remove previous number's index if it exists
    public void change(int index, int number)
    {
        if (idxToNum.containsKey(index))
        {
            int prevNum = idxToNum.get(index);
            numToIdx.get(prevNum).remove(index); // O(log n)
            if (numToIdx.get(prevNum).isEmpty()) 
            {
                numToIdx.remove(prevNum); // O(1)
            }
        }

        // Step 2: Update index mappings
        idxToNum.put(index, number);
        numToIdx.putIfAbsent(number, new TreeSet<>());
        numToIdx.get(number).add(index); // O(log n)
    }

    // Step 3: Retrieve the smallest index for a given number
    public int find(int number) {
        if (numToIdx.containsKey(number))
        {
            return numToIdx.get(number).first(); // O(1)
        }
        return -1;
    }
}
```
``` C++ []
class NumberContainers
{
private:
    unordered_map<int, int> idxToNum; // Stores index → number mapping
    map<int, set<int>> numToIdx;      // Stores number → ordered set of indices

public:
    NumberContainers() {}

    // Step 1: If index exists, remove it from the previous number’s index set
    void change(int index, int number)
    {
        if (idxToNum.count(index))
        {
            int prevNum = idxToNum[index];
            numToIdx[prevNum].erase(index); // O(log n)
            
            if (numToIdx[prevNum].empty())
            {
                numToIdx.erase(prevNum); // O(1)
            }
        }

        // Step 2: Update mappings
        idxToNum[index] = number;
        numToIdx[number].insert(index); // O(log n)
    }

    // Step 3: Find the smallest index for a given number
    int find(int number)
    {
        if (numToIdx.count(number))
        {
            return *numToIdx[number].begin(); // O(1)
        }
        
        return -1;
    }
};
```
['Hash Table', 'Tree', 'Design', 'Ordered Map', 'Rolling Hash', 'Sorting', 'Heap (Priority Queue)', 'Ordered Set', 'C++', 'Java']