3 Sorted collections approach in C#
Intuition\n\nWe need to maintain 3 sorted sequences. \n\nThe tricky part is, there is no good way to represent sorted Sequences in C#, so we will create one.\n\
# Intuition\n\nWe need to maintain 3 sorted sequences. \n\nThe tricky part is, there is no good way to represent sorted Sequences in C#, so we will create one.\n\n# Approach\n\nOne thing should be obvious. At first, we are just adding elements to a sequence, but eventually we first need to \'pop\' the oldest adding element. You can either use Queue or LinkedList or circle array implementation, whatever you find easiest.\n\nRemoving an element procedure:\n1. Find a collection with the element and delete the element from it.\n2. Rebalance the left collection to contain k elements and mid collection to contain m - 2 * k elements. The right collection will then always end up with k elements.\n\nAdding an element procedure: \n\n1. Add to the left.\n2. If left size is larger than k, move largest element to mid\n3. If mid dize is larger than m - 2 * k, move largest element to right.\n\nWhenever an element enters or leaves the mid collection, we add/subtract its value from the sum.\n\nIn C#, SortedSet is nice because it has O(1) Min/Max fields. But it can only contain unique elements.\n\nTo mitigate that, we can combine it with a Dictionary to keep track of element counts.  \n\n# Code\n```\npublic class MKAverage {\n\n    public MKAverage(int m, int k) {\n        this.m = m;\n        this.k = k;\n\n        midSize = m - 2 * k;\n        window = new int[m];\n        index = 0;\n        left = new CustomSortedList();\n        mid = new CustomSortedList();\n        right = new CustomSortedList();\n    }\n    \n    public void AddElement(int num) {\n        var realIndex = index % m;\n        if (index >= m) {\n            var old = window[realIndex];\n            Remove(old);\n        }\n\n        Add(num);\n        window[realIndex] = num;\n        index++;\n    }\n\n    private void Remove(int n) {\n        if (n <= left.Max) {\n            left.Remove(n);\n        }\n        else if (n <= mid.Max) {\n            mid.Remove(n);\n            sum -= n;\n        }\n        else {\n            right.Remove(n);\n        }\n\n        if (left.Count < k) {\n            var moved = Move(mid, left, true);\n            sum -= moved;\n        }\n\n        if (mid.Count < midSize) {\n            var moved = Move(right, mid, true);\n            sum += moved;\n        }\n    }\n\n    private int Move(CustomSortedList from, CustomSortedList to, bool min) {\n        var n = min ? from.Min : from.Max;\n        from.Remove(n);\n        to.Add(n);\n        return n; \n    }\n\n    private void Add(int n) {\n        left.Add(n);\n\n        if (left.Count > k) {\n            var moved = Move(left, mid, false);\n            sum += moved;\n        }\n\n        if (mid.Count > midSize) {\n            var moved = Move(mid, right, false);\n            sum -= moved;\n        }\n    }\n    \n    public int CalculateMKAverage() {\n        return (index < m) ? -1 : sum / midSize; \n    }\n\n    private int midSize;\n    private int index;\n    private int[] window;\n    private int sum;\n\n    private CustomSortedList left;\n    private CustomSortedList mid;\n    private CustomSortedList right;\n\n    private class CustomSortedList {\n        public CustomSortedList() {\n            counts = new Dictionary<int, int>();\n            set = new SortedSet<int>();\n        }\n\n        public void Add(int n) {\n            if (counts.ContainsKey(n)) {\n                counts[n]++;\n            }\n            else {\n                counts[n] = 1;\n                set.Add(n);\n            }\n\n            Count++;\n        }\n\n        public void Remove(int n) {\n            if (!counts.TryGetValue(n, out var count)) {\n                return;\n            }\n\n            if (count > 1) {\n                counts[n] -= 1;\n            }\n            else {\n                counts.Remove(n);\n                set.Remove(n);\n            }\n\n            Count--;\n        }\n\n        public int Count {get; private set; } \n\n        public int Max => set.Max;\n        public int Min => set.Min;\n\n        private Dictionary<int, int> counts;\n        private SortedSet<int> set;\n    }\n\n    private int m;\n    private int k;\n}\n\n```
['C#']