2349

2349. Design a Number Container System (Medium)

Design a number container system that can do the following:

• Insert or Replace a number at the given index in the system.
• Return the smallest index for the given number in the system.

Implement the NumberContainers class:

• NumberContainers() Initializes the number container system.
• void change(int index, int number) Fills the container at index with the number. If there is already a number at that index, replace it.
• int find(int number) Returns the smallest index for the given number, or -1 if there is no index that is filled by number in the system.

 

Example 1:

Input
["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]
[[], [10], [2, 10], [1, 10], [3, 10], [5, 10], [10], [1, 20], [10]]
Output
[null, -1, null, null, null, null, 1, null, 2]

Explanation
NumberContainers nc = new NumberContainers();
nc.find(10); // There is no index that is filled with number 10. Therefore, we return -1.
nc.change(2, 10); // Your container at index 2 will be filled with number 10.
nc.change(1, 10); // Your container at index 1 will be filled with number 10.
nc.change(3, 10); // Your container at index 3 will be filled with number 10.
nc.change(5, 10); // Your container at index 5 will be filled with number 10.
nc.find(10); // Number 10 is at the indices 1, 2, 3, and 5. Since the smallest index that is filled with 10 is 1, we return 1.
nc.change(1, 20); // Your container at index 1 will be filled with number 20. Note that index 1 was filled with 10 and then replaced with 20. 
nc.find(10); // Number 10 is at the indices 2, 3, and 5. The smallest index that is filled with 10 is 2. Therefore, we return 2.

 

Constraints:

• 1 <= index, number <= 109
• At most 105 calls will be made in total to change and find.

Companies: Google

Related Topics:
Hash Table, Design, Heap (Priority Queue), Ordered Set

Similar Questions:

• Seat Reservation Manager (Medium)
• Design a Food Rating System (Medium)

Hints:

• Use a hash table to efficiently map each number to all of its indices in the container and to map each index to their current number.
• In addition, you can use ordered set to store all of the indices for each number to solve the find method. Do not forget to update the ordered set according to the change method.

Solution 1.

// OJ: https://leetcode.com/problems/design-a-number-container-system
// Author: github.com/lzl124631x
// Time:
//      NumberContainers: O(1)
//      change: O(logN)
//      find: O(1)
// Space: O(N)
class NumberContainers {
    unordered_map<int, int> indexToNumber;
    unordered_map<int, set<int>> numberToIndices;
public:
    NumberContainers() {
    }
    void change(int index, int number) {
        if (indexToNumber.count(index)) {
            int oldNumber = indexToNumber[index];
            numberToIndices[oldNumber].erase(index);
            if (numberToIndices[oldNumber].empty()) numberToIndices.erase(oldNumber);
        }
        indexToNumber[index] = number;
        numberToIndices[number].insert(index);
    }
    int find(int n) {
        if (numberToIndices.count(n) == 0) return -1;
        return *numberToIndices[n].begin();
    }
};