Java Solutions For Two Follow-ups
1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?\n\nWe can use an array with 100 slots to store the count of each num
**1. If all integer numbers from the stream are between 0 and 100, how would you optimize it?**\n\nWe can use an array with 100 slots to store the count of each number, and then iterate through the array to find the median.\nAs the size of the array is 101, the time complexity of finding the median is constant.\n\n***Java Sample Code:***\n```\nclass MedianFinder {\n    int[] arr;\n    int size;\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        arr = new int[101];\n        size = 0;\n    }\n    \n    public void addNum(int num) {\n        arr[num]++;\n        size++;\n    }\n    \n    public double findMedian() {\n        int index = 0, median = size / 2, first = 0;\n        for(int i = 0; i < 101; i++) {\n            for(int j = 0; j < arr[i]; j++) {\n                if(index == median - 1) first = i;\n                else if(index == median) {\n                    if(size % 2 == 0) return (first + i) / 2.0;\n                    else return (double) i;\n                }\n                index++;\n            }\n        }\n        return -1;\n    }\n}\n```\n\n**2. If 99% of all integer numbers from the stream are between 0 and 100, how would you optimize it?**\n\nIt\'s similar to above, but here are situations we need to talk about.\n\n1. If we can make sure we will call `findMedian()` only when we already have most of integer numbers inserted, which assure the median would appear between 0 and 100, we can just use a variable to store the total size of all numbers and the number of elements that are less than 0 respectively and don\'t have to care about what those numbers are. For those numbers that are greater than 100, we don\'t have to really care about them to find median as we will iterate through from the lowest number.\n\n***Java Sample Code***\n```\nclass MedianFinder {\n    int[] arr;\n    int size;\n    int lo;\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        arr = new int[101];\n        size = 0;\n        lo = 0;\n    }\n    \n    public void addNum(int num) {\n        if(num < 0) lo++;\n        else if(num <= 100 && num >= 0) arr[num]++;\n        size++;\n    }\n    \n    public double findMedian() {\n        int index = lo, median = size / 2, first = 0;\n        for(int i = 0; i < 101; i++) {\n            for(int j = 0; j < arr[i]; j++) {\n                if(index == median - 1) first = i;\n                else if(index == median) {\n                    if(size % 2 == 0) return (first + i) / 2.0;\n                    else return (double) i;\n                }\n                index++;\n            }\n        }\n        return -1;\n    }\n}\n```\n\n\n2. But if we don\'t know when we will call `findMedian()`, we have to make sure we have access to all numbers inserted all the time. Especially, if we insert numbers that are not in the range of 0 to 100 at the very beginning and we call `findMedian`, we need to be able to access those numbers and find the median between them. So we need two more PriorityQueues to help store numbers that are less than 0 or greater than 100.\nWhy ***PriorityQueue***? As PriorityQueue helps sort the number when we insert it, we could easily find the median by iterating through the PriorityQueue if the median is in one of the PriorityQueue.\n\n***Java Sample Code***\n```\nclass MedianFinder {\n    int[] arr;\n    int size;\n    PriorityQueue<Integer> lo;\n    PriorityQueue<Integer> hi;\n    /** initialize your data structure here. */\n    public MedianFinder() {\n        arr = new int[101];\n        size = 0;\n        lo = new PriorityQueue<Integer>();\n        hi = new PriorityQueue<Integer>();\n    }\n    \n    public void addNum(int num) {\n        if(num < 0) lo.add(num);\n        else if(num > 100) hi.add(num);\n        else arr[num]++;\n        size++;\n    };\n    \n    public double findMedian() {\n        int median = size / 2, index;\n        PriorityQueue<Integer> temp;\n        // If total size is odd number\n        if(size % 2 != 0) {\n            if(median < lo.size()) {\n                // The median is in lo\n\t\t\t\t// Todo:\n            }\n            else if(median >= size - hi.size()) {\n                // The median is in hi\n\t\t\t\t// Todo:\n            } \n            else {\n                // The median is in arr\n\t\t\t\t// Todo:\n            }\n        } // If total size is even number\n        else {\n            int a, b;\n            if(median < lo.size()) {\n                temp = new PrirotyQueue<>(lo);\n                index = 0;\n                while(index < median) {\n                    if(index == median - 1) {\n                        a = temp.poll();\n                        b = temp.poll();\n                        return (a + b) / 2.0;\n                    } else {\n                        temp.poll();    \n                        index++;\n                    }\n                }\n            } else if(median == lo.size()) {\n                int last = 0;\n                temp = new PrirotyQueue<>(lo);\n                while(!temp.isEmpty()) last = temp.poll();\n                for(int i = 0; i < 101; i++)\n                    if(arr[i] != 0) \n                        return (i + last) / 2.0;\n            } else if(median > size - hi.size()) {\n                temp = new PrirotyQueue<>(hi);\n                index = size - hi.size();\n                while(index < median) {\n                    if(index == median - 1) {\n                        a = temp.poll();\n                        b = temp.poll();\n                        return (a + b) / 2.0;\n                    } else {\n                        temp.poll();\n                        index++;\n                    }\n                }\n            } else if(median == size - hi.size()) {\n                int first = hi.peek();\n                for(int i = 100; i >= 0; i--)\n                    if(arr[i] != 0)\n                        return (i + first) / 2.0;                \n            } else {\n                // The median is in arr\n\t\t\t\t// Todo:\n            }\n        }\n        return 0.0;\n    }\n}\n\n/**\n * Your MedianFinder object will be instantiated and called as such:\n * MedianFinder obj = new MedianFinder();\n * obj.addNum(num);\n * double param_2 = obj.findMedian();\n */\n ```\n
['Java']