Efficient Index Management Using Dictionary and SortedSet for Quick Updates and Retrievals
IntuitionThe problem requires efficiently updating values at specific indices and retrieving the smallest index associated with a given number.
A dictionary _co
# Intuition
##### The problem requires efficiently updating values at specific indices and retrieving the smallest index associated with a given number.
 - A dictionary `_container` is useful for direct access to stored numbers at each index.
 - A sorted set `SortedSet<int>` maintains indices for each number in sorted order, allowing quick retrieval of the minimum index.

# Approach
1. Use a Dictionary `_container`

    - Maps `index → number`, allowing efficient updates when a number at an index changes.
    
2. Use a Dictionary of Sorted Sets `_minIndexes`
    - Maps `number → SortedSet<int>`, which maintains a set of indices in sorted order for quick access to the smallest index.
    - When a number is removed from an index, it is also removed from its corresponding `SortedSet<int>`.
    - If a `SortedSet<int>` becomes empty, it is removed from `_minIndexes` to save space.
    
3. Operations:

    - `Change(index, number)`:
        - If index is already in `_container`, remove it from the previous number’s `SortedSet<int>`.
        - Add the index to the `SortedSet<int>` for the new number.
        - Update `_container` with the new mapping.
    - `Find(number)`:
        - Retrieve the smallest index from `SortedSet<int>`.
        - If the number doesn’t exist, return `-1`.

# Complexity
- Time complexity:
    - `Change(index, number)`:
        - Dictionary Lookup: `O(1)`
        - SortedSet<int>.Remove(): `O(log N)`
        - SortedSet<int>.Add(): `O(log N)`
        - Overall: `O(log N)`
        
    - `Find(number)`:
        - Dictionary Lookup:`O(1)`
        - SortedSet<int>.Min: `O(1)`
        - Overall: `O(1)`

- Space complexity:
    - `O(N)` for storing at most `N` indices in `_container` and `_minIndexes`.

# Code
```csharp []
public class NumberContainers {
    private Dictionary<int, int> _container;
    private Dictionary<int, SortedSet<int>> _minIndexes;

    public NumberContainers() {
        _container = new();
        _minIndexes = new();
    }
    
    public void Change(int index, int number) {
        if (_container.TryGetValue(index, out int prevValue)) {
            if (_minIndexes.TryGetValue(prevValue, out var prevSet)) {
                prevSet.Remove(index);
                if (prevSet.Count == 0) _minIndexes.Remove(prevValue);
            }
        }
        _minIndexes.TryAdd(number, new SortedSet<int>());
        _minIndexes[number].Add(index);
        
        _container[index] = number;
    }
    
    public int Find(int number) {
         return _minIndexes.TryGetValue(number, out var indexes)
            ? indexes.Min 
            : -1;
    }
}
```
['C#']