✅ Easy to Understand | 2 Approaches | Hash Table with PQ or TreeSet | Detailed Video Explanation🔥
IntuitionThe problem requires efficiently mapping indices to numbers while supporting quick updates and retrieval of the smallest index for a given number. Usin
# Intuition
The problem requires efficiently mapping indices to numbers while supporting quick updates and retrieval of the smallest index for a given number. Using a HashMap for direct index-to-number mapping and a TreeSet for sorted index retrieval ensures both operations remain efficient.

# Approach
1. Use a `HashMap<Integer, Integer>` (`map`) to store the mapping of indices to numbers.
2. Use another `HashMap<Integer, TreeSet<Integer>>` (`valIdx`) to maintain a mapping from each number to a sorted set of indices.
3. In the `change` method:
   - If the index is already associated with a different number, remove it from the old number's `TreeSet`.
   - Update the index-to-number mapping.
   - Add the index to the `TreeSet` corresponding to the new number.
4. In the `find` method:
   - If the number exists in `valIdx`, return the smallest index from its `TreeSet`.
   - Otherwise, return `-1`.

# Complexity
- Time complexity:
  - `change(index, number)`: $$O(\log N)$$ due to `TreeSet` operations (insertion and deletion).
  - `find(number)`: $$O(1)$$ as retrieving the first element from a `TreeSet` is constant time.

- Space complexity:
  - $$O(N)$$, where $$N$$ is the number of indices stored, since we maintain mappings in `map` and `valIdx`.


# Code
```java []
class NumberContainers {

    // Map to store index -> number mapping
    Map<Integer, Integer> map;

    // Map to store number -> set of indices mapping.  Using TreeSet for sorted indices.
    Map<Integer, TreeSet<Integer>> valIdx;

    public NumberContainers() {
        map = new HashMap<>();
        valIdx = new HashMap<>();    
    }
    
    // O(log(N)) time complexity due to TreeSet operations (remove and add). N is the number of indices.
    public void change(int index, int number) {
        if(!map.containsKey(index)){        // New entry
            map.put(index, number);
        }else{          // Replacement of an existing entry
            int oldnumber = map.get(index);
            map.put(index, number);

            // Remove the old index from the TreeSet associated with the old number.
            valIdx.get(oldnumber).remove(index);

            // If the TreeSet for the old number becomes empty, remove the entry from valIdx.
            if(valIdx.get(oldnumber).isEmpty())
                valIdx.remove(oldnumber);
        }

        // Add the new index to the TreeSet associated with the new number.
        if(!valIdx.containsKey(number)){
            valIdx.put(number, new TreeSet<Integer>());
        }
        valIdx.get(number).add(index);
    }
    
    // O(1) time complexity.  Accessing a HashMap and getting the first element from a TreeSet are constant time operations.
    public int find(int number) {   
        if(!valIdx.containsKey(number))
            return -1; // Number not found
        return valIdx.get(number).first(); // Return the smallest index (first element in the sorted TreeSet).
    }
}

/**
 * Your NumberContainers object will be instantiated and called as such:
 * NumberContainers obj = new NumberContainers();
 * obj.change(index,number);
 * int param_2 = obj.find(number);
 */
```

https://youtu.be/zxs-KagiwhA


['Hash Table', 'Design', 'Heap (Priority Queue)', 'Ordered Set', 'Java']