How to Design a Data Structure that supports insertion,deletion of (key,value) pairs and fetching of minimum and maximum value in O(1) time?

Question

1. plus(String key, Integer value) - O(1) plus should add 1 to the existing value if the key is already there, else should insert 0 for that key

2. minus(String key, Integer value) - O(1) minus should subtract 1 from the existing value if the key is already there

3. getMin() - O(1) returns the minimum element from the data structure

4. getMax() - O(1) returns the maximum element from the data structure

Answer 1

This problem can be solved in O(1) time for all operations using the data structure presented in this paper which also solves the LFU problem in O(1) time worst case for all operations. http://dhruvbird.com/lfu.pdf

I suspect that the problem on Leetcode and the other one about LFU https://leetcode.com/problems/lfu-cache/description/ both derive their inspiration from the same paper.

Disclosure: I’m one of the authors of that paper.

Answer 2

Since the question is not very clear, I assume getMin/getMax return the minimum/maximum pair (with priority to keys) and minus remove a pair when its existing value is set 0.

This is simply impossible using only key comparisons, and very hard (if not impossible) without comparisons.

---

Here is the proof:

Let's assume such a data structure S exists and use only comparisons (at least for the keys). The following algorithm which sort a list of strings could be executed in O(n) time.

function(lstIn : List of string) -> List of string
    s := empty data structure S
    n := length(lstInt)

    for i in 0 .. n
        str := ith item of lstIn
        s.plus(str, 0)
    end for

    lstOut := empty list
    for i in 0 .. n
        key,value := s.getMin()
        s.minus(key, value)
        append key to lstOut
    end for

    return lstOut
end function

However, comparison-based sorting algorithms need at least Ω(n log n) comparisons for most inputs. Thus, the data structure S cannot exist.

---

What about not using comparisons?

If key are unbounded strings, it is probably impossible to design such an algorithm too since it would probably require an impracticable amount of resources (there it no practical known algorithm to do that in the state of the art).

If key are small bounded strings, such an algorithm could exists since O(n) comparison-less string-based sorting algorithms already exist (see radix sort). In this case, you can actually design a specific data structure enabling the computation of the four operations in amortized O(1) based on radix-tree and radix-sorting.

Answer 3

Here's what I understand the question is:

void plus(string key): adds 1 to existing value or inserts 0 if not existing
void minus(string key): subtracts 1 to existing value if existing
getMin(): minimum value
getMax(): maximum value

I have assumed that plus(String key, Integer value) is a typo since the question doesn't clear what's the use of value.

Solution: This one is tricky but I think this is certainly possible. Primarily because we're just incrementing and decrementing the values by 1.

I always prefer using linked list when you want to have some ordering among the elements and also want to update these values - especially when there's insertion and removal. In this case, I order the linked list by value.

Let us maintain the following data members:

list<int> ll; // linked list that holds "values". Increasing order of values.
unordered_map<string,int> m; // hashmap containing key to value mapping
unordered_map<string,int> count; // hashmap containing value to count mapping
unordered_map<int,list<int>::iterator> value_to_ll; // hashmap containing value to linked list node mapping

Now I think the picture may be getting clearer. I'll give my best quick try to implement void minus(string key):

void minus(string key)
{
    // check if key is present
    if (!m.count(key)) return;

    int minvalue = ll.front();
    int maxvalue = ll.back();
    int original_value = m[key];
    // decrement value
    m[key]--;
    // decrement count of original value
    count[original_value]--;
    // increment count of new value
    count[m[key]]++;

    // if orignal value was the minvalue, decrement minvalue
    if (original_value == minvalue)
    {
        minvalue--;
    }
    // if original value was the only maxvalue, decrement the maxvalue
    if (original_value == maxvalue)
    {
        if (count[original_value] == 0) maxvalue--;
    }

    // insert new node for new value if not exists
    if (value_to_ll.count(m[key]) == 0)
    {
        ll.insert(value_to_ll[original_value], m[key]);
    }

    // decrement count of original value and remove it if 0
    if (count[original_value] == 0)
    {
        count.erase(original_value);
        ll.erase(value_to_ll[original_value]);
    }
}

The code has not been tested and may fail. This is to just give you an idea on how you can use linked list and hashmap to get things done in constant time.

Similarly you can implement void plus(string key). min and max are super easy to find out - first and last element of the linked list respectively.