Design Idea to achieve all O(1) - Criticism welcomed!


  • 0
    O

    Disclaimer: This post does not have any code.

    My idea is(expressed in c++ data structs), to first have a struct:

    struct data{
        string key;
        int val;
    }
    

    to have an unordered_map of <key, list_iterator<data>>, and also have an unordered_map of <value, list<data>>. We keep track of the min and max values as single variables, call them iMin and iMax.

    Insertion is O(1)

    If the value is new

    Insertion is simply adding to the unordered_map<value, list<data>>, and adding into unordered_map<key, iterator>. Update iMax.

    If the value is old

    Insertion actually removes the node from the associated value's bucket and move it to the next, higher one. Update the data.val. Update iMax and iMin respectively.

    Deletion is O(1)

    STD library's delete is fine for list, O(1), and it's O(1) since we can get the list_iterator<data>* node in O(1). Update iMax and iMin respectively

    Max and min are O(1)

    Return the two variables iMin and iMax we kept internal to the data structure.

    How does this idea sound? I know it has a high memory overhead but all the operations are O(1).


  • 0
    T

    I don't quite understand the rest of your design. But here there is definitely a problem:

    @oneraynyday said in Design Idea to achieve all O(1) - Criticism welcomed!:

    Update iMax and iMin respectively

    If you delete iMax or iMin, how will you find a new value for them in O(1)?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.