2349. Design a Number Container System

• categories: Code, Interview Question, leetcode, Medium
• source: https://leetcode.com/problems/design-a-number-container-system/
• topics: Heap, Hash Table

Description

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.

Idea

• Hash Tables + heaps

Code

class NumberContainers:
    def __init__(self):
        self.number_indices = {}
        self.indices = defaultdict(list)
        
 
    def change(self, index: int, number: int) -> None:
        self.number_indices[index] = number
        heappush(self.indices[number], index)
 
    def find(self, number: int) -> int:
        while self.indices[number]:
            index = self.indices[number][0] 
            if self.number_indices[index] == number:
                return index
            heappop(self.indices[number])
        return -1