other.number_container_system

A number container system that uses binary search to delete and insert values into arrays with O(log n) write times and O(1) read times.

This container system holds integers at indexes.

Further explained in this leetcode problem > https://leetcode.com/problems/minimum-cost-tree-from-leaf-values

Classes

NumberContainer

Module Contents

class other.number_container_system.NumberContainer

binary_search_delete(array: list | str | range, item: int) → list[int]

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

binary_search_insert(array: list | str | range, index: int) → list[int]

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

change(index: int, number: int) → None

Changes (sets) the index as number

>>> cont = NumberContainer()
>>> cont.change(0, 10)
>>> cont.change(0, 20)
>>> cont.change(-13, 20)
>>> cont.change(-100030, 20032903290)

find(number: int) → int

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

indexmap: dict[int, int]

numbermap: dict[int, list[int]]