Problem Statement
Brute Force [TLE]
class NumberContainers:
def __init__(self):
self.hash_map = defaultdict(int)
def change(self, index: int, number: int) -> None:
self.hash_map[index] = number
def find(self, number: int) -> int:
values = set(k for k, v in self.hash_map.items() if v == number)
if not values:
return -1
return min(values)
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
Editorial
Approach 1: Two Maps
class NumberContainers:
def __init__(self):
# Initializing the defaultdict with SortedSet and the regular dictionary
# Map from number to set of indices
self.number_to_indices = collections.defaultdict(SortedSet)
# Map from index to number
self.index_to_number = {}
def change(self, index: int, number: int) -> None:
# If index already has a number, remove it from the old number's index set
if index in self.index_to_number:
previous_number = self.index_to_number[index]
self.number_to_indices[previous_number].remove(index)
if not self.number_to_indices[previous_number]:
del self.number_to_indices[previous_number]
# Update the number and add the index to the new number's set
self.index_to_number[index] = number
self.number_to_indices[number].add(index)
def find(self, number: int) -> int:
# Return the smallest index for the given number, or -1 if not found
if number in self.number_to_indices and self.number_to_indices[number]:
return self.number_to_indices[number][0]
return -1
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
Approach 2: Using Min Heap with Lazy Update
class NumberContainers:
def __init__(self):
# Map to store number -> min heap of indices
self.number_to_indices = defaultdict(list)
# Map to store index -> number
self.index_to_numbers = {}
def change(self, index: int, number: int) -> None:
# Update index to number mapping
self.index_to_numbers[index] = number
# Add index to the min heap for this number
heapq.heappush(self.number_to_indices[number], index)
def find(self, number: int) -> int:
# If number doesn't exist in our map
if not self.number_to_indices[number]:
return -1
# Keep checking top element until we find valid index
while self.number_to_indices[number]:
index = self.number_to_indices[number][0]
# If index still maps to our target number, return it
if self.index_to_numbers.get(index) == number:
return index
# Otherwise remove this stale index
heapq.heappop(self.number_to_indices[number])
return -1
# Your NumberContainers object will be instantiated and called as such:
# obj = NumberContainers()
# obj.change(index,number)
# param_2 = obj.find(number)
