Design a Number Container System

Problem Statement

The task is to design a system capable of storing and managing numbers indexed in a specific way. Each number can be inserted or replaced at a designated index, and the system should be able to quickly retrieve the smallest index that contains a specified number. The system will be embodied within a NumberContainers class, which supports two primary operations:

1. Changing the number at a specific index. If the index already contains a number, it will be replaced with the new number.
2. Finding the smallest index that holds a particular number. Should the number not exist in any index, the system should return -1.

Using this system, users can manage indexed numbers effectively, enabling both rapid updates and efficient retrievals based on the number's value.

Examples

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.

Approach and Intuition

The challenge primarily revolves around managing a dynamic mapping between numbers and their indices efficiently. Here's how one might think about tackling this problem:

1. Data Structures:

   • For mapping numbers to their smallest indices efficiently, we can use a dictionary where keys are the numbers and values are sorted sets of indices.
   • Each entry in the dictionary represents all indices containing a specific number. A sorted set assists in finding the smallest index quickly.

2. Operations:

   • Initialization (NumberContainers constructor):
     • Prepare the necessary data structures with no initial data. This setup involves initializing an empty dictionary for the mappings.
   • Change Number at Index (change method):
     • If the index is already mapped to a different number, remove that index from the corresponding number's set. Update or add the index to the new number's set.
     • This ensures that each number maintains only the relevant indices where it is present.
   • Find Smallest Index (find method):
     • Simply access the sorted set for the queried number and retrieve the smallest index if available. If the number is not found, return -1.

3. Performance Considerations:

   • As the operations need to handle up to 10^5 calls, efficient data manipulations are key. Using a dictionary with sorted structures allows for amortized fast access and updates.
   • Maintaining sorted sets ensures that the minimum index retrieval is always optimized.

Following this approach ensures that the system is both efficient and easy to manage, even as numbers and their corresponding indices change frequently over numerous operations.

Solutions

class NumbContainer {
public:
    NumbContainer() {}
    
    void update(int idx, int num) {
        idxToNum[idx] = num;
        numToIdx[num].push(idx);
    }
    
    int locate(int num) {
        if (numToIdx.find(num) == numToIdx.end()) {
            return -1;
        }
    
        auto& indicesHeap = numToIdx[num];
    
        while (!indicesHeap.empty()) {
            int i = indicesHeap.top();
    
            if (idxToNum[i] == num) {
                return i;
            }
    
            indicesHeap.pop();
        }
    
        return -1;
    }
    
private:
    unordered_map<int, priority_queue<int, vector<int>, greater<int>>> numToIdx;
    unordered_map<int, int> idxToNum;
};
    
/**
 * Your NumbContainer object will be instantiated and called as such:
 * NumbContainer* obj = new NumbContainer();
 * obj->update(idx,num);
 * int param_2 = obj->locate(num);
 */