Design a Number Container System — LeetCode 2349 Python Solution

The problem

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.

Example

Input

["NumberContainers", "find", "change", "change", "change", "change", "find", "change", "find"]

Output

[null, -1, null, null, null, null, 1, null, 2]

Explanation

NumberContainers nc = new NumberContainers();

Python solution

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)

Complexity

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 2349. Design a Number Container System is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Related problems