#2349

Design a Number Container System

specialist · 765 · lc medium +31 · 57.1% accepted · 966 likes · top 52%

Description

Build a data structure that maps integer indices to integer values and can efficiently answer the following queries:

- Insert or overwrite the value stored at a given index.

- Report the smallest index that currently holds a given value.

Implement the NumberContainers class:

- NumberContainers() constructs the container system.

- void change(int index, int number) stores number at position index, replacing any existing value.

- int find(int number) returns the minimum index storing number, or -1 if none exists.

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]

Example 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.

Code

class NumberContainers:

    def __init__(self):
        

    def change(self, index: int, number: int) -> None:
        

    def find(self, number: int) -> int:
        


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

class NumberContainers:

    def __init__(self):
        

    def change(self, index: int, number: int) -> None:
        

    def find(self, number: int) -> int:
        


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