Using 2 Maps
Intuition\nWe need to keep track of what number each index holds [Map 1] (it can hold only one) and what all indices hold the number n [Map 2] (it is an ordered
# Intuition\nWe need to keep track of what number each index holds [Map 1] (it can hold only one) and what all indices hold the number n [Map 2] (it is an ordered set as more than one index can have number n). \n\n# Approach\nWe have two maps to store both of these details (unordered maps as we access by value and the order does not matter). Each time we assign a number to the index, we check if it already holds a number. If it does, we remove the index from the number in Map 2, change the number assigned to the index in Map 1. If the index does not hold any number currently, we simply assign a number to that index in Map 1 and insert to the map in Map 2. When we have to find the lowest index that has the number n, we can search in Map 2 and get the smallest index as the first index of the ordered set. \n\n# Complexity\n- Time complexity:\nWhile adding to Map 1 - O(1)\nWhile adding to Map 2 - O(logn) as we have to add the index to the set in an ordered manner. \nDeleting from Map 2 from the ordered set - O(n) \n\n\n# Code\n```\nclass NumberContainers {\npublic:\n    unordered_map<int,int> mp;\n    unordered_map<int,set<int>> m;\n\n    NumberContainers() {\n        \n    }\n    \n    void change(int index, int number) {\n        if(this->mp[index] != number) {\n            int prev_num = this->mp[index];\n            auto it = this->m[prev_num].find(index);  \n            this->m[prev_num].erase(*it); \n            this->mp[index] = number;\n        }\n\n        this->m[number].insert(index);\n    }\n    \n    int find(int number) {\n        if(this->m[number].size()==0) return -1;\n        return *this->m[number].begin();\n    }\n};
['Hash Table', 'C++']