Is Design a Number Container System easy or hard?

The problem is rated Medium because the logic requires coordinating multiple data structures and handling updates correctly. The individual operations are simple, but maintaining consistency between mappings and ensuring the smallest index is returned makes it slightly tricky.

Design a Number Container System Python or Java solution

Python implementations typically use a dictionary with heapq for each number and lazy deletion to remove outdated indices. Java solutions often use HashMap combined with TreeSet, allowing direct retrieval of the smallest index using first(). Both achieve O(log n) operations.

How to solve Design a Number Container System in O(log n)?

Maintain two mappings: indexToNumber to track the current value at each index, and numberToIndices which stores all indices for a number in a sorted structure like TreeSet or a min heap. Updates adjust the index membership, while queries return the smallest stored index. Ordered structures ensure O(log n) insertion and removal.

What is the best approach for Design a Number Container System?

The most reliable approach uses a HashMap and an ordered set (such as TreeSet). A map stores index -> number while another map stores number -> sorted set of indices. Each change operation updates both structures and find(number) simply returns the smallest index from the set. Both operations run in O(log n) time with O(n) space.

Is Design a Number Container System asked at Google/Amazon/Meta?

Design-style data structure problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. The question evaluates understanding of hash maps, heaps, and ordered sets along with the ability to maintain consistent state across multiple data structures.

What data structure is used in Design a Number Container System?

The core structures are hash tables for constant-time mapping and either an ordered set (TreeSet / SortedSet) or a min heap to maintain the smallest index for each number. These structures together allow efficient updates and queries.

What is the time complexity of Design a Number Container System?

Using the optimal design, both change(index, number) and find(number) run in O(log n) time because indices are inserted or removed from a balanced ordered set or heap. Hash map lookups remain O(1). Overall space complexity is O(n) to store mappings between indices and numbers.

Description Hints 2 Solution Video 30:33

2349. Design a Number Container System

Medium57.1% acceptance1 company

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 <= 10⁹
At most 10⁵ calls will be made in total to change and find.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

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.

Hint 2

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.

30:33

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution