aboutsummaryrefslogtreecommitdiff
path: root/design_number_container.py
blob: c3436776ac350d58cf0aacfa562a5c7d610792ef (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
# 2349. Design a Number Container System
from collections import defaultdict
from bisect import insort_left

"""
design a number container system that can do the following: insert or replace
a number at the given index in the system or return the smallest index for
the given number in the system. implement the 'NumberContainers' class.
"""


class NumberContainers(object):
    def __init__(self):
        self.idxs = {}
        self.nums = defaultdict(list)

    def change(self, index, number):
        """
        :type index: int
        :type number: int
        :rtype: None
        """
        if index in self.idxs:
            old = self.idxs[index]
            self.nums[old].remove(index)
        self.idxs[index] = number
        insort_left(self.nums[number], index)

    def find(self, number):
        """
        :type number: int
        :rtype: int
        """
        return -1 if not self.nums[number] else self.nums[number][0]


if __name__ == "__main__":
    obj = NumberContainers()
    print(obj.find(10))
    obj.change(2, 10)
    obj.change(1, 10)
    obj.change(3, 10)
    obj.change(5, 10)
    print(obj.find(10))
    obj.change(1, 20)
    print(obj.find(10))