Using min-max heaps: beats 90% time / 100% memory
Intuition\nThe goal hele is to prvide a way of querying for some statistics over the sorted order of a dynamic set of elements - the previous m values at the mo
# Intuition\nThe goal hele is to prvide a way of querying for some statistics over the sorted order of a dynamic set of elements - the previous $$m$$ values at the moment we are queried. Obviously, this can be accomplished by sorting the set of previous $$m$$ items each time we are queried, but in order to be efficient, the solution must maintain these elements (somewhat) sorted.\n\nNote that items that came before the previous $$m$$ elements should not be taken into consideration anymore, so we also have to handle their expiration appropriately.\n\n# Approach\nIn first place, a queue (`q`) is used to keep track of the previous $$m$$ values received from stream.\n\nFor keeping the $$m - 2k$$ middle elements of sorted order, this solution used a simple (not optimal) implementation of min-max heaps (`mid`). Also, the sum of these elements is stored and continuously updated so that **querying operation** takes $$O(1)$$ time to compute the average.\n\nFinally, to handle the expiration of values, other two min-max heaps (`l` and `r`) are maintained for the lowest and highest $$k$$ values. Also, the values are stored along with a `heapId` and indices (min and max) for locating it in the heap where it currently belongs.\n\nWith these in place, every time a new value is received, we first check if the queue is at its capacity, in which case the first entry in the queue must be expired. Then the new entry is inserted both in the queue and in the heaps.\n\nNote that whenever we expire an entry or insert a new one into the heaps, they must be "rebalanced" to keep their size. Since min-max heaps are employed, this can be easily done by removing the lowest (or highest) value from a heap and pushing it to the neighboring heap.\n\n# Complexity\n- Time complexity:\n$$O(M)$$ for `Constructor`, since we preallocate an array of size $$m$$ when creating the slice `q`.\n$$O(logM)$$ for each `AddElement` operation.\n$$O(1)$$ for each `CalculateMKAverage` operation.\n\n- Space complexity:\n$$O(M+2M)$$, being $$O(M)$$ for the queue and $$O(2M)$$ for the whole set of heaps.\n\n# Code\n```\nimport (\n    "container/heap"\n)\n\ntype MKNode struct {\n    val int\n    heapId int\n    minIdx, maxIdx int\n}\n\ntype MKMinHeap []*MKNode\ntype MKMaxHeap []*MKNode\n\nfunc (h MKMinHeap) Len() int { return len(h) }\nfunc (h MKMaxHeap) Len() int { return len(h) }\nfunc (h MKMinHeap) Less(i, j int) bool { return h[i].val < h[j].val }\nfunc (h MKMaxHeap) Less(i, j int) bool { return h[i].val > h[j].val }\nfunc (h MKMinHeap) Swap(i, j int) {\n    h[i], h[j] = h[j], h[i]\n    h[i].minIdx = i\n    h[j].minIdx = j\n}\nfunc (h MKMaxHeap) Swap(i, j int) {\n    h[i], h[j] = h[j], h[i]\n    h[i].maxIdx = i\n    h[j].maxIdx = j\n}\nfunc (h *MKMinHeap) Push(v any) {\n    n := len(*h)\n    node := v.(*MKNode)\n    node.minIdx = n\n    *h = append(*h, node)\n}\nfunc (h *MKMaxHeap) Push(v any) {\n    n := len(*h)\n    node := v.(*MKNode)\n    node.maxIdx = n\n    *h = append(*h, node)\n}\nfunc (h *MKMinHeap) Pop() any {\n    tmp := *h\n    size := len(tmp)\n    node := tmp[size-1]\n    node.minIdx = -1\n    tmp[size-1] = nil\n    *h = tmp[:size-1]\n    return node\n}\nfunc (h *MKMaxHeap) Pop() any {\n    tmp := *h\n    size := len(tmp)\n    node := tmp[size-1]\n    node.maxIdx = -1\n    tmp[size-1] = nil\n    *h = tmp[:size-1]\n    return node\n}\n\ntype MKHeap interface {\n    Len() int\n    Min() *MKNode\n    Max() *MKNode\n    PopMin() *MKNode\n    PopMax() *MKNode\n    Push(n *MKNode)\n    Remove(minIdx int)\n}\n\ntype mkHeap struct {\n    id int\n    minHeap MKMinHeap\n    maxHeap MKMaxHeap\n}\n\nfunc NewMKHeap(id int) MKHeap {\n    minHeap := MKMinHeap{}\n    heap.Init(&minHeap)\n    maxHeap := MKMaxHeap{}\n    heap.Init(&maxHeap)\n    return &mkHeap{id, minHeap, maxHeap}\n}\n\nfunc (h *mkHeap) Len() int { return h.minHeap.Len() }\nfunc (h *mkHeap) Min() *MKNode { return h.minHeap[0] }\nfunc (h *mkHeap) Max() *MKNode { return h.maxHeap[0] }\nfunc (h *mkHeap) PopMin() *MKNode {\n    n := heap.Pop(&h.minHeap).(*MKNode)\n    heap.Remove(&h.maxHeap, n.maxIdx)\n    n.maxIdx = -1\n    n.heapId = -1\n    return n\n}\nfunc (h *mkHeap) PopMax() *MKNode {\n    n := heap.Pop(&h.maxHeap).(*MKNode)\n    heap.Remove(&h.minHeap, n.minIdx)\n    n.minIdx = -1\n    n.heapId = -1\n    return n\n}\nfunc (h *mkHeap) Push(n *MKNode) {\n    n.heapId = h.id\n    heap.Push(&h.minHeap, n)\n    heap.Push(&h.maxHeap, n)\n}\nfunc (h *mkHeap) Remove(minIdx int) {\n    n := heap.Remove(&h.minHeap, minIdx).(*MKNode)\n    n.minIdx = -1\n    heap.Remove(&h.maxHeap, n.maxIdx)\n    n.maxIdx = -1\n    n.heapId = -1\n}\n\ntype MKAverage struct {\n    m, k int\n    q []*MKNode\n    l, mid, r MKHeap\n    midSum int\n}\n\nfunc Constructor(m int, k int) MKAverage {\n    q := make([]*MKNode, 0, m)\n    l := NewMKHeap(0)\n    mid := NewMKHeap(1)\n    r := NewMKHeap(2)\n    return MKAverage{m, k, q, l, mid, r, 0}\n}\n\nfunc (this *MKAverage) AddElement(num int)  {\n    if len(this.q) == this.m {\n        this.expire()\n    }\n    newNode := &MKNode{val: num}\n    this.q = append(this.q, newNode)\n    this.r.Push(newNode)\n    for this.r.Len() > this.k {\n        n := this.r.PopMin()\n        this.mid.Push(n)\n        this.midSum += n.val\n    }\n    for this.mid.Len() > (this.m-2*this.k) {\n        n := this.mid.PopMin()\n        this.midSum -= n.val\n        this.l.Push(n)\n    }\n}\n\nfunc (this *MKAverage) CalculateMKAverage() int {\n    if len(this.q) < this.m {\n        return -1\n    }\n    return int(this.midSum / (this.m-2*this.k))\n}\n\nfunc (this *MKAverage) expire() {\n    expired := this.q[0]\n    if expired.heapId == 2 {\n        this.r.Remove(expired.minIdx)\n        n := this.l.PopMax()\n        this.mid.Push(n)\n        this.midSum += n.val\n        n = this.mid.PopMax()\n        this.midSum -= n.val\n        this.r.Push(n)\n    } else if expired.heapId == 1 {\n        this.mid.Remove(expired.minIdx)\n        this.midSum -= expired.val\n        n := this.l.PopMax()\n        this.mid.Push(n)\n        this.midSum += n.val\n    } else {\n        this.l.Remove(expired.minIdx)\n    }\n    this.q[0] = nil\n    this.q = this.q[1:]\n}\n\n\n/**\n * Your MKAverage object will be instantiated and called as such:\n * obj := Constructor(m, k);\n * obj.AddElement(num);\n * param_2 := obj.CalculateMKAverage();\n */\n```
['Queue', 'Heap (Priority Queue)', 'Data Stream', 'Go']