#2349

Medium

LeetCode Problem Workspace

Design a Number Container System

Learn to implement a Number Container System using hash tables and design techniques to efficiently track numbers and indices.

hash table design heap priority queue ordered set

Problem Statement

Design a system that manages numbers in indexed containers with two operations: change the number at a specific index and find the smallest index for a given number. Each index can be updated multiple times, and you must always track the current number at every index.

Implement the NumberContainers class supporting the following methods: change(index, number) updates the number at the given index, and find(number) returns the smallest index currently holding that number, or -1 if none exist. Ensure that your implementation handles up to 10^5 operations efficiently with indices and numbers up to 10^9.

Examples

Example 1

Input: See original problem statement.

Output: See original problem statement.

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.

Solution Approach

Use Hash Maps for Fast Lookup

Maintain a hash map mapping each number to a sorted structure of indices where it appears. Also maintain a map from indices to current numbers to quickly update the system when a change occurs. This setup directly addresses the Hash Table plus Design pattern.

Handle Updates Efficiently

When changing a number at an index, first remove the index from the old number's set if present, then insert it into the new number's set. Using a priority queue or ordered set for each number ensures find operations always retrieve the smallest index efficiently.

Optimize for Time Complexity

All operations rely on log(n) time complexity due to maintaining ordered sets for each number. The system avoids scanning all indices by using hash maps for number-to-indices mapping, keeping both change and find operations fast under heavy workloads.

Complexity Analysis

Metric	Value
Time	O(\log n)
Space	O(n)

Time complexity for change and find is O(log n) because updating or retrieving from a sorted set of indices per number takes logarithmic time. Space complexity is O(n) since we store mappings for each index and for all indices per number.

What Interviewers Usually Probe

Check if candidate uses both number-to-indices and index-to-number maps correctly.
Observe whether updates remove indices from previous numbers before insertion.
Watch for correct handling of find when no index exists for a number.

Common Pitfalls or Variants

Common pitfalls

Failing to remove an index from the old number's set before updating can produce incorrect find results.
Not using a sorted structure for indices may return the wrong smallest index.
Assuming indices are contiguous leads to inefficient O(n) searches instead of using hash maps.

Follow-up variants

Return all indices for a number instead of just the smallest.
Support batch updates to multiple indices at once.
Restrict number ranges to 1-1000 to simplify storage but maintain design logic.

FAQ

What data structures are recommended for Design a Number Container System?

Use hash maps to track number-to-indices and index-to-number relationships, and ordered sets or priority queues to maintain sorted indices for each number.

How do I handle duplicate updates at the same index?

Always remove the index from the previous number's set before inserting it into the new number's set to ensure find returns the correct smallest index.

What is the time complexity of find and change operations?

Both operations run in O(log n) time because insertion and removal in a sorted set of indices take logarithmic time.

Can numbers be negative or very large?

Yes, numbers can go up to 10^9 and indices as well, so using efficient hash maps and ordered sets is necessary for performance.

How does this problem exemplify the Hash Table plus Design pattern?

It combines hash table mapping for quick lookups with careful design of ordered index tracking to satisfy both update and retrieval constraints efficiently.

terminal

Solution

Solution 1: Hash Table + Ordered Set

We use a hash table $d$ to record the mapping relationship between indices and numbers, and another hash table $g$ to record the set of indices corresponding to each number. Here, we can use an ordered set to store the indices, which allows us to conveniently find the smallest index.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

class NumberContainers:

    def __init__(self):
        self.d = {}
        self.g = defaultdict(SortedSet)

    def change(self, index: int, number: int) -> None:
        if index in self.d:
            old_number = self.d[index]
            self.g[old_number].remove(index)
        self.d[index] = number
        self.g[number].add(index)

    def find(self, number: int) -> int:
        ids = self.g[number]
        return ids[0] if ids else -1


# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)

Continue Practicing

#2353 design a food rating system #2336 smallest number in infinite set #2424 longest uploaded prefix