2349: Design-a-Number-Container-System
Medium

Initially, I thought about using 2 unordered_maps to track both index_to_number and number_to_index.

There are 2 ways to store the list of indices that I implemented: using a set and a minimum heap (with a priority_queue).

Initially, I planned on erasing the previous number located at index_to_number[index] everytime the change function was called. However, I realized that for larger indices, there is a small chance they will ever be called by find, so we should only think about pop-ing them if we really need to.

Therefore, we just build the pop-ing functionality into the find function, by starting from the smallest index in number_to_index[number] (let us denote this as i) and checking whether or not index_to_number[i] == number.

Finally, if all that fails, we just return -1

Then, if we repeat this for all the inputs, we have a working algorithm on our hands! (finally)

Code:

// Set
class NumberContainers {
public:
    NumberContainers() {}
    
    void change(int index, int number) {
        index_to_number[index] = number;
        number_to_index[number].insert(index);
    }
    
    int find(int number) {
        if (number_to_index[number].size() == 0) {
            return -1;
        }
        auto p = prev(number_to_index[number].end());
        while(number_to_index[number].size() > 0 && index_to_number[*p] != number) {
            number_to_index[number].erase(p);
            --p;
        }
        return number_to_index[number].size() == 0 ? -1 : *p;
    }
private:
    unordered_map<int, int> index_to_number;  
    unordered_map<int, set<int, greater<int>>> number_to_index;
};

// priority_queue (min-heap)
class NumberContainers {
public:
    NumberContainers() {}
    
    void change(int index, int number) {
        index_to_number[index] = number;
        number_to_index[number].push(index);
    }
    
    int find(int number) {
        if (number_to_index[number].size() == 0) {
            return -1;
        } else {
            while ((number_to_index[number].size() > 0) && index_to_number[number_to_index[number].top()] != number) {
                number_to_index[number].pop();
            }
            return empty(number_to_index[number]) ? -1 : number_to_index[number].top();
        }
    }
private:
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> number_to_index;
    unordered_map<int, int> index_to_number;
};

Complexity: