Design a Number Container System

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

• index_to_number would provide the number present at a specific index
• number_to_index would provide a list of indices for a specific number

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.

• if index_to_number[i] == number, then we can just return i
• if index_to_number[i] != number, then we can just pop it and carry on until we find an index that satisifies the requirements

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

• Time: O(log n) for change and O(k log n) for find
• Space: O(n)