LC-2349 Medium LeetCode

2349. Design a Number Container System

Hash Table Design Heap (Priority Queue) Ordered Set

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 57% Topics: Hash Table, Design, Heap (Priority Queue), Ordered Set

Reading material

Arrays & Hashing 12 min Design (Data Structures) 14 min Heaps & Priority Queues 13 min

Reference solution (spoiler · python)

# Time:  ctor:   O(1)
#        change: O(logn)
#        find:   O(1)
# Space: O(n)

from sortedcontainers import SortedList


# sorted list
class NumberContainers(object):

    def __init__(self):
        self.__idx_to_num = {}
        self.__num_to_idxs = collections.defaultdict(SortedList)

    def change(self, index, number):
        """
        :type index: int
        :type number: int
        :rtype: None
        """
        if index in self.__idx_to_num:
            self.__num_to_idxs[self.__idx_to_num[index]].remove(index)
            if not self.__num_to_idxs[self.__idx_to_num[index]]:
                del self.__num_to_idxs[self.__idx_to_num[index]]
        self.__idx_to_num[index] = number
        self.__num_to_idxs[number].add(index)

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

Solution from kamyu104/LeetCode-Solutions · MIT