a number container system that uses binary search to delete and insert values into arrays with olog n write times and o1 read times this container system holds integers at indexes further explained in this leetcode problem https leetcode comproblemsminimumcosttreefromleafvalues numbermap keys are the number and its values are lists of indexes sorted in ascending order indexmap keys are an index and it s values are the number at that index removes the item from the sorted array and returns the new array numbercontainer binarysearchdelete1 2 3 2 1 3 numbercontainer binarysearchdelete0 0 0 0 0 0 numbercontainer binarysearchdelete1 1 1 1 1 1 numbercontainer binarysearchdelete1 0 0 1 numbercontainer binarysearchdelete1 0 1 0 numbercontainer binarysearchdeleterange7 3 0 1 2 4 5 6 numbercontainer binarysearchdelete1 1 2 2 3 3 2 2 1 1 3 3 numbercontainer binarysearchdeleteabcde c a b d e numbercontainer binarysearchdelete0 1 2 4 0 traceback most recent call last valueerror either the item is not in the array or the array was unsorted numbercontainer binarysearchdelete2 0 4 1 11 1 traceback most recent call last valueerror either the item is not in the array or the array was unsorted numbercontainer binarysearchdelete125 1 traceback most recent call last typeerror binarysearchdelete only accepts either a list range or str inserts the index into the sorted array at the correct position numbercontainer binarysearchinsert1 2 3 2 1 2 2 3 numbercontainer binarysearchinsert0 1 3 2 0 1 2 3 numbercontainer binarysearchinsert5 3 0 0 11 103 51 5 3 0 0 11 51 103 numbercontainer binarysearchinsert5 3 0 0 11 100 103 101 5 3 0 0 11 100 101 103 numbercontainer binarysearchinsertrange10 4 0 1 2 3 4 4 5 6 7 8 9 numbercontainer binarysearchinsertabd c a b c d numbercontainer binarysearchinsert131 23 traceback most recent call last typeerror binarysearchinsert only accepts either a list range or str if the item already exists in the array insert it after the existing item if the item doesn t exist in the array insert it at the appropriate position changes sets the index as number cont numbercontainer cont change0 10 cont change0 20 cont change13 20 cont change100030 20032903290 remove previous index set new index number not seen before or empty so insert number value here we need to perform a binary search insertion in order to insert the item in the correct place returns the smallest index where the number is cont numbercontainer cont find10 1 cont change0 10 cont find10 0 cont change0 20 cont find10 1 cont find20 0 simply return the 0th index smallest of the indexes found or 1 numbermap keys are the number and its values are lists of indexes sorted in ascending order indexmap keys are an index and it s values are the number at that index removes the item from the sorted array and returns the new array numbercontainer binary_search_delete 1 2 3 2 1 3 numbercontainer binary_search_delete 0 0 0 0 0 0 numbercontainer binary_search_delete 1 1 1 1 1 1 numbercontainer binary_search_delete 1 0 0 1 numbercontainer binary_search_delete 1 0 1 0 numbercontainer binary_search_delete range 7 3 0 1 2 4 5 6 numbercontainer binary_search_delete 1 1 2 2 3 3 2 2 1 1 3 3 numbercontainer binary_search_delete abcde c a b d e numbercontainer binary_search_delete 0 1 2 4 0 traceback most recent call last valueerror either the item is not in the array or the array was unsorted numbercontainer binary_search_delete 2 0 4 1 11 1 traceback most recent call last valueerror either the item is not in the array or the array was unsorted numbercontainer binary_search_delete 125 1 traceback most recent call last typeerror binary_search_delete only accepts either a list range or str inserts the index into the sorted array at the correct position numbercontainer binary_search_insert 1 2 3 2 1 2 2 3 numbercontainer binary_search_insert 0 1 3 2 0 1 2 3 numbercontainer binary_search_insert 5 3 0 0 11 103 51 5 3 0 0 11 51 103 numbercontainer binary_search_insert 5 3 0 0 11 100 103 101 5 3 0 0 11 100 101 103 numbercontainer binary_search_insert range 10 4 0 1 2 3 4 4 5 6 7 8 9 numbercontainer binary_search_insert abd c a b c d numbercontainer binary_search_insert 131 23 traceback most recent call last typeerror binary_search_insert only accepts either a list range or str if the item already exists in the array insert it after the existing item if the item doesn t exist in the array insert it at the appropriate position changes sets the index as number cont numbercontainer cont change 0 10 cont change 0 20 cont change 13 20 cont change 100030 20032903290 remove previous index set new index number not seen before or empty so insert number value here we need to perform a binary search insertion in order to insert the item in the correct place returns the smallest index where the number is cont numbercontainer cont find 10 1 cont change 0 10 cont find 10 0 cont change 0 20 cont find 10 1 cont find 20 0 simply return the 0th index smallest of the indexes found or 1
class NumberContainer:
    def __init__(self) -> None:
        
        
        self.numbermap: dict[int, list[int]] = {}
        
        self.indexmap: dict[int, int] = {}

    def binary_search_delete(self, array: list | str | range, item: int) -> list[int]:
        
        if isinstance(array, (range, str)):
            array = list(array)
        elif not isinstance(array, list):
            raise TypeError(
                "binary_search_delete() only accepts either a list, range or str"
            )

        low = 0
        high = len(array) - 1

        while low <= high:
            mid = (low + high) // 2
            if array[mid] == item:
                array.pop(mid)
                return array
            elif array[mid] < item:
                low = mid + 1
            else:
                high = mid - 1
        raise ValueError(
            "Either the item is not in the array or the array was unsorted"
        )

    def binary_search_insert(self, array: list | str | range, index: int) -> list[int]:
        
        if isinstance(array, (range, str)):
            array = list(array)
        elif not isinstance(array, list):
            raise TypeError(
                "binary_search_insert() only accepts either a list, range or str"
            )

        low = 0
        high = len(array) - 1

        while low <= high:
            mid = (low + high) // 2
            if array[mid] == index:
                
                
                array.insert(mid + 1, index)
                return array
            elif array[mid] < index:
                low = mid + 1
            else:
                high = mid - 1

        
        array.insert(low, index)
        return array

    def change(self, index: int, number: int) -> None:
        
        
        if index in self.indexmap:
            n = self.indexmap[index]
            if len(self.numbermap[n]) == 1:
                del self.numbermap[n]
            else:
                self.numbermap[n] = self.binary_search_delete(self.numbermap[n], index)

        
        self.indexmap[index] = number

        
        if number not in self.numbermap:
            self.numbermap[number] = [index]

        
        
        else:
            self.numbermap[number] = self.binary_search_insert(
                self.numbermap[number], index
            )

    def find(self, number: int) -> int:
        
        
        return self.numbermap.get(number, [-1])[0]


if __name__ == "__main__":
    import doctest

    doctest.testmod()