Java Multiset/TreeMap solution without storing all values
The idea is to maintain a TreeMap and a mid value along with its relative index to it\'s count.\nEach time a number is added the relative index is incremented o
The idea is to maintain a TreeMap<Number, Count> and a mid value along with its relative index to it\'s count.\nEach time a number is added the relative index is incremented or decremented.\n\nFor example if we have numbers 10, 10, 10, 15, **15**, 15, 20, 20, 20\nThe map contains:\n10: 3\n15: 3\n20: 3\nmid value is 15 and the relative index is 1 (pointing to the second 15)\n\nWhen another 20 is added it becomes\nmap:\n10: 3\n15: 3\n20: 4\nmid value is still 15 and the relative index is 2 (pointing to the third 15)\n\nAnother 20:\n10: 3\n15: 3\n20: 5\nmid value is still 20 and the relative index is 0 (pointing to the first 20)\n\n```\nclass MedianFinder {\n\n    private final TreeMap<Integer, Integer> tree = new TreeMap<>();\n    private int totalCount;\n\n    private int midValue;\n    private int midIndex;\n\n    /** initialize your data structure here. */\n    public MedianFinder() {\n    }\n\n    public void addNum(int num) {\n        tree.put(num, tree.getOrDefault(num, 0) + 1);\n        totalCount++;\n\n        if (totalCount == 1) {\n            midValue = num;\n            midIndex = 0;\n        } else {\n            if (num >= midValue) {\n                midIndex++;\n                if (midIndex / 2 >= tree.get(midValue)) {\n                    midValue = tree.higherKey(midValue);\n                    midIndex = 0;\n                }\n            } else {\n                midIndex--;\n                if (midIndex < 0) {\n                    midValue = tree.lowerKey(midValue);\n                    midIndex = tree.get(midValue) * 2 - 1;\n                }\n            }\n        }\n    }\n\n    public double findMedian() {\n        if (totalCount % 2 == 0 && (midIndex + 1) / 2 >= tree.get(midValue)) {\n            int nextMidValue = tree.higherKey(midValue);\n            return (midValue + nextMidValue) / 2d;\n        } else {\n            return midValue;\n        }\n    }\n}\n```
[]