HashMap | TreeSet | Solution for LeetCode#2349
IntuitionThe goal is to efficiently track the smallest index associated with a given number. By using two maps, we can maintain the current number at each index
![image.png](https://assets.leetcode.com/users/images/3dfc6287-571f-485b-a1d7-04e2179acebe_1738986153.2757611.png)

# Intuition
<!-- Describe your first thoughts on how to solve this problem. -->
The goal is to efficiently track the smallest index associated with a given number. By using two maps, we can maintain the current number at each index and the sorted list of indices for each number.

# Approach
<!-- Describe your approach to solving the problem. -->
1. Map Initialization:
	- `map` stores the current number at each index.
	- `valIdx` maps each number to a sorted set of indices where the number appears.
2. Change Operation:
	- If the number is not in `valIdx`, initialize it with an empty sorted set.
	- If the index already has a number, remove the index from the sorted set of the previous number.
	- Add the index to the sorted set of the new number and update `map`.
3. Find Operation:
	- Return the smallest index from the sorted set of the given number. If the set is empty, return `-1`.
	
# Complexity
- Time complexity: O(log n)
<!-- Add your time complexity here, e.g. $$O(n)$$ -->

- Space complexity: O(n)
<!-- Add your space complexity here, e.g. $$O(n)$$ -->

# Code
```java []
import java.util.NoSuchElementException;

class NumberContainers {
    Map<Integer, Integer> map; // Stores the number at each index
    Map<Integer, TreeSet<Integer>> valIdx; // Maps each number to a sorted set of indices

    // Constructor to initialize the maps
    public NumberContainers() {
        map = new HashMap<>();
        valIdx = new HashMap<>();
    }

    // Method to change the number at a given index
    public void change(int index, int number) {
        // If the number is not in valIdx, initialize it with an empty sorted set
        if (!valIdx.containsKey(number)) {
            valIdx.put(number, new TreeSet<>());
        }

        // If the index already has a number, update the frequency map
        if (map.containsKey(index)) {
            if(map.get(index)==number) return;
            int prevVal = map.get(index);
            valIdx.get(prevVal).remove(index); // Remove the index from the sorted set of the previous number
        }

        // Add the index to the sorted set of the new number
        valIdx.get(number).add(index);
        // Update the map with the new number at the given index
        map.put(index, number);
    }

    // Method to find the smallest index for a given number
    public int find(int number) {
        // If the number is in valIdx, return the smallest index from the sorted set
        if (valIdx.containsKey(number)) {
            try {
                return valIdx.get(number).first();
            } catch (NoSuchElementException e) {
                return -1;
            }
        }
        // If the number is not found, return -1
        return -1;
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index,number);
 * int param_2 = obj.find(number);
 */
```
```python []
from collections import defaultdict
from sortedcontainers import SortedSet

class NumberContainers(object):

    def __init__(self):
        self.map={}
        self.valIdx=defaultdict(SortedSet)

    def change(self, index, number):
        """
        :type index: int
        :type number: int
        :rtype: None
        """
        if index in self.map:
            if self.map[index]==number: 
                return 
            preVal=self.map[index]
            self.valIdx.get(preVal).remove(index)
        
        self.valIdx[number].add(index)
        self.map[index]=number


    def find(self, number):
        """
        :type number: int
        :rtype: int
        """
        if number not in self.valIdx or not self.valIdx[number]:
            return -1
        return self.valIdx[number][0]


# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
```


['Python', 'Java', 'Python3']