Design a number container system that can do the following:
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 <= 109105 calls will be made in total to change and find.In this approach, we use two main data structures:
The initial idea is to map each index to its number and, for each number, keep a sorted set of indices where the number occurs. This allows us to quickly access the smallest index for any number.
This Python implementation uses the sortedcontainers library to efficiently maintain a sorted set of indices for each number. The change method updates the current index with the new number and ensures indices for the old number are updated. The find method returns the smallest index from the sorted set.
Java
Time Complexity:
change: O(log N), where N is the number of indices tracked for a number.
find: O(1) on average since accessing the minimum index is direct.
Space Complexity: O(N + M), where N is the number of indices and M is the number of unique numbers.
In this approach, we can optimize by using two hash maps:
indexToNumber to map each index to its current number.numberToIndices to map each number to a min-heap of indices (using a custom data structure).This provides efficient data management for the system with an alternative focus on comprehensive hash map manipulation.
This C++ implementation uses an unordered map to track the number at each index and a set for sorted index tracking for each number. Both data structures allow for efficient operations on updates and retrievals.
JavaScript
Time Complexity:
change: O(log N) due to set operations.
find: O(1) by accessing the first element of a set.
Space Complexity: O(N + M), where N and M are sizes of index and number maps.
| Approach | Complexity |
|---|---|
| Using HashMaps and SortedMap | Time Complexity: |
| Using Two HashMaps | Time Complexity: |
Design a Number Container System | 2 Approaches | Leetcode 2349 | codestorywithMIK • codestorywithMIK • 7,208 views views
Watch 9 more video solutions →Practice Design a Number Container System with our built-in code editor and test cases.
Practice on FleetCode