Today’s problem

https://leetcode.com/problems/design-a-number-container-system/description/

Intuition

In this question, we need to find the smallest index of the number in the list. Note that the index may change when dealing with the list. Because we need the smallest index, so we need a sorted datastructure. Trick: We can get a lazy tag that stores the number of each index, so that we can pop only when we find our current answer does not fullfill the requirement.

Approach

  1. Store a dictionary that stores the sorted sequence of the numbers and the index.
  2. Store a dictionary of index and numbers pair.
  3. Check whether the answer is valid in the find function.

Complexity

  • Time complexity: $O(Q\ times log(N))$, Q is the time of query, N is the size of the dictionary.

  • Space complexity: $O(Q)$, Q is the time of query.

Code

class NumberContainers:

    def __init__(self):
        self.lst = dict()
        self.idx = dict()

    def change(self, index: int, number: int) -> None:
        if number not in self.lst:
            self.lst.update({number: []})

        heappush(self.lst[number], index)
        self.idx.update({index: number})

    def find(self, number: int) -> int:
        if number not in self.lst:
            return -1
        while self.lst[number]:
            currIndex = self.lst[number][0]
            if self.idx[currIndex] != number:
                heappop(self.lst[number])
            else:
                return currIndex
        return -1


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

image.png