Design a Number Container System

main.md

Question

Approach

Today is more of designing.

I took a heap-based approach to optimize finding the smallest index efficiently.

For the __init__ magic function, I created a dictionary index_to_number to map indices to their assigned numbers and another dictionary, number_to_indices, where each number maps to a min-heap that stores all indices containing that number.

For change(), I first check if the index already has a number. If it does, I mark the old number’s entry as invalid using (float('inf'), index) instead of removing it directly. Then, I update the index with the new number and push it into the heap.

For find(), I retrieve the smallest index from the heap but ensure it is still valid. If the top of the heap corresponds to a removed or updated entry, I pop it and continue until I find a valid one.

Implementation

import heapq

class NumberContainers:
    def __init__(self):
        self.index_to_number = {}
        self.number_to_indices = {}
    
    def change(self, index: int, number: int) -> None:
        if index in self.index_to_number:
            old_number = self.index_to_number[index]
            if old_number in self.number_to_indices:
                heapq.heappush(self.number_to_indices[old_number], (float('inf'), index))
        
        self.index_to_number[index] = number
        if number not in self.number_to_indices:
            self.number_to_indices[number] = []
        heapq.heappush(self.number_to_indices[number], (index, index))

    def find(self, number: int) -> int:
        if number in self.number_to_indices:
            while self.number_to_indices[number]:
                min_index, actual_index = self.number_to_indices[number][0]
                if actual_index in self.index_to_number and self.index_to_number[actual_index] == number:
                    return actual_index
                heapq.heappop(self.number_to_indices[number])
        return -1

Complexities

• Time
  • init: O(1)
  • change: O(logn)
  • find: O(logn)
• Space:
  • init: O(1)
  • change: O(n)
  • find: O(n)

🔥🔥