Detailed Solution | HashMap | Prefix Sum | O(n)
Problem Description\nThese are numbers in the array that collectively make up the majority (n - 2) of the array element.\nAnd from rest 2 one is sum of these sp
# Problem Description\nThese are numbers in the array that collectively make up the majority (n - 2) of the array element.\nAnd from rest 2 one is sum of these special number and one outliner.\nWe have to find out the maximum possible value of this outliner. \n\n\n# Intuition\nFrom problem we can say that nums = [[specail number], special numbers sum , outliner]\nTherefor :- Sum of nums = 2*Special_number_Sum + outliner\n\nNow we can jusy calculate sum and use HashMap to find out the sum.\n# Approach \n1. Create a HashMap to dtore all the values in array.\n2. Store sum of array in a variable.\n3. Now traverse array and substract element from the sum.\n4. Then resultant sum will contain the sum of special elements as we well all special elements so resultant sum will always even.\n    i.e temp_sum%2==0 \n5. Now check for temp_sum in HashMap if found store that array element in HashMap and also check if nums[ i ] == temp_sum, then occurance of temp_sum should be >1.\n\n\n# Complexity\n- Time complexity: O(n)\n\n- Space complexity: O(n)\n\n# Code\n```java []\nclass Solution {\n    public int getLargestOutlier(int[] nums) {\n        int n = nums.length;\n        int sum = 0;\n        HashMap<Integer,Integer> h = new HashMap<>();\n        int max = Integer.MIN_VALUE;\n        for(int i : nums) {\n            sum += i;\n            h.put(i,h.getOrDefault(i,0)+1);\n        }\n        for(int i : nums){\n            int sum_left = (sum-i);\n            if(sum_left%2!=0) {\n                continue;\n            }\n            if(h.containsKey(sum_left/2)){\n                if(sum_left/2!=i) max = Math.max(max,i);\n                if(sum_left/2==i && h.get(i)>1) max = Math.max(max,i);\n                 \n            }\n        }\n        return max;\n\n    }\n}\n```\n```c++ []\nclass Solution {\npublic:\n    int getLargestOutlier(vector<int>& nums) {\n        int n = nums.size();\n        int sum = 0;\n        std::unordered_map<int, int> h;\n        int max = INT_MIN;\n        \n        for (int i : nums) {\n            sum += i;\n            h[i]++;\n        }\n\n        for (int i : nums) {\n            int sum_left = sum - i;\n            if (sum_left % 2 != 0) {\n                continue;\n            }\n            int target = sum_left / 2;\n            if (h.count(target)) {\n                if (target != i) max = std::max(max, i);\n                if (target == i && h[i] > 1) max = std::max(max, i);\n            }\n        }\n        return max;\n          \n    }\n};\n```\n```python []\nclass Solution(object):\n    def getLargestOutlier(self, nums):\n        n = len(nums)\n        total_sum = sum(nums)\n        freq = {}\n        max_val = float(\'-inf\')\n        \n        for num in nums:\n            freq[num] = freq.get(num, 0) + 1\n        \n        for num in nums:\n            sum_left = total_sum - num\n            if sum_left % 2 != 0:\n                continue\n            target = sum_left // 2\n            if target in freq:\n                if target != num:\n                    max_val = max(max_val, num)\n                elif target == num and freq[num] > 1:\n                    max_val = max(max_val, num)\n        \n        return max_val\n        \n```
['Array', 'Hash Table', 'Math', 'Hash Function', 'Python', 'C++', 'Java']