Find median in constant time O(1)

Question

I have a stream of operations. Each operation is one of:

1. Set a number value V at key K
2. Remove key K

Only one operation can be executed at a time. I need to keep track of the median of all set values in O(1) time.

Example: Initial state:

values == {}
median == 0

Execute set(0, 5):

values == {0: 5}
median == 5

Execute set(1, 3):

values == {0: 5, 1: 3}
median == 4

Execute set(2, 1):

values == {0: 5, 1: 3, 2: 1}
median == 3

Execute set(1, 10):

values == {0: 5, 1: 10, 2: 1}
median == 5

Execute remove(1):

values == {0: 5, 2: 1}
median == 3

I need to keep track only the median value. I don't care if the numbers in hashmap are stored or not. The set and remove must run in O(1) time. ALTHOUGH the parameters to these functions may be computed in any time complexity(e.g., the sorted index of a number can be computed outside set and be passed as a parameter to set and only verified that it is correct inside of the set function)

I tried computing the necessary sorted indices and passing them as parameters to set and remove but I am not sure how to do it bug free.

Answer 1

I can only see one option to do something like this. Store the collection as a linked list, which will preserve the order and do the insert operation for O(1). The median at insertion can also be modified for O(1). In this case, the insertion location must be specified by the key of the previous node.

Here is c# code:

// linked list to keep an order
var list = new LinkedList<int>();

// hash table to get a node by key
var nodeByKey = new Dictionary<int, LinkedListNode<int>>();

// linked list node with number n/2
LinkedListNode<int>? medianNode = null;


void Print()
{
    var pairsStrings = nodeByKey
        .OrderBy(pair => pair.Value.Value)
        .Select(pair => $"{pair.Key}: {pair.Value.Value}");
    Console.WriteLine("values == {" + string.Join(", ", pairsStrings) + "}");
    Console.WriteLine("median == " + Median());
    Console.WriteLine();
}

Print();

Set(0, 5, KeyOfPreviousNodeForSetValue(5));
Print();

Set(1, 3, KeyOfPreviousNodeForSetValue(3));
Print();

Set(2, 1, KeyOfPreviousNodeForSetValue(1));
Print();

Remove(1);
Set(1, 10, KeyOfPreviousNodeForSetValue(10));
Print();

Remove(1);
Print();


void Set(int k, int v, int keyOfPreviousNode = -1)
{
    bool isKeyFound = nodeByKey.ContainsKey(k);
    if(isKeyFound) throw new Exception("key already exists");

    LinkedListNode<int> newNode;

    if (keyOfPreviousNode < 0)
    {
        // if keyOfPreviousNode < 0 then trying to insert to first positioin

        if (list.Count > 0)
        {
            var firstNode = list.First;
            if (firstNode!.Value < v) throw new Exception("position is not right");
        }
        newNode = list.AddFirst(v);
    }
    else
    {
        // if previousNode is specified then trying to insert after him

        bool isPrevNodeFound = nodeByKey.TryGetValue(keyOfPreviousNode, out var previousNode);
        if (!isPrevNodeFound) throw new Exception("previousNode not found");

        if (previousNode!.Value > v) throw new Exception("position is not right");

        var nextNode = previousNode.Next;
        if (nextNode != null && nextNode.Value < v) throw new Exception("position is not right");

        newNode = list.AddAfter(previousNode, v);
    }

    nodeByKey[k] = newNode;

    // update median
    if(list.Count == 0)
        medianNode = null;
    else if(list.Count == 1)
        medianNode = list.First;
    else
    {
        bool isShifted = newNode.Value <= medianNode!.Value;
        bool isOdd = list.Count % 2 == 1;

        if (isShifted && !isOdd)
            medianNode = medianNode.Previous;

        if (!isShifted && isOdd)
            medianNode = medianNode!.Next;
    }

}
void Remove(int k)
{
    bool isKeyFound = nodeByKey.TryGetValue(k, out var nodeToRemove);
    if(!isKeyFound) throw new Exception("key not found");

    var prevMedianNode = medianNode?.Previous;
    var nextMedianNode = medianNode?.Next;
    int removedValue = nodeToRemove!.Value;

    list.Remove(nodeToRemove!);
    nodeByKey.Remove(k);

    // update median
    if (list.Count == 0)
        medianNode = null;
    else if (list.Count == 1)
        medianNode = list.First;
    else
    {
        bool isShifted = removedValue <= medianNode!.Value;
        bool isEven = list.Count % 2 == 0;

        if (medianNode != nodeToRemove)
        {
            prevMedianNode = medianNode?.Previous;
            nextMedianNode = medianNode?.Next;
        }

        if (isShifted && !isEven)
            medianNode = nextMedianNode;

        if (!isShifted && isEven)
            medianNode = prevMedianNode;

        if (isShifted && isEven)
            medianNode = prevMedianNode;
    }
}

float Median()
{
    if(medianNode == null) 
        return 0;
    else if(list.Count % 2 == 1) 
        return medianNode.Value;
    else 
        return (float)(medianNode.Value + medianNode.Next!.Value) / 2;
}


int KeyOfPreviousNodeForSetValue(int v)
{
    // I dont care for complexity here

    LinkedListNode<int>? prevNode = null;
    for (var node = list.First; node != null; node = node.Next)
    {
        if(node.Value > v) break;
        prevNode = node;
    }

    if (prevNode == null) return -1;

    return nodeByKey.First(pair => pair.Value == prevNode).Key;
}

The difference from your example is that you can't immediately insert an existing key here.

Also, I didn't care at all about the complexity of finding a parameter of location to insert. Although this could be improved, but but not to O(1).