🔥Beats 100 % 🔥 | O(n) and O(1)  | ✔️ Explained & Optimized Solution ✔️ |
\n\n\n### Intuition:\nThe goal is to find the largest "outlier" in the array. An outlier is defined as a number that is neither one of the original special numb
![image.png](https://assets.leetcode.com/users/images/3d074712-d6e7-4895-89c7-e87f033f9cd4_1733083280.2554307.png)\n\n\n### Intuition:\nThe goal is to find the largest "outlier" in the array. An outlier is defined as a number that is neither one of the original special numbers nor the element representing the sum of those numbers.\n\nTo solve this:\n1. First, we compute the total sum of the array.\n2. Then, for each number in the array, we check if removing it results in an even sum and if half of that sum is present in the array.\n3. If it is, we consider that number as a valid "outlier" and track the largest such outlier.\n\n---\n\n### Approach:\n1. **Compute the Total Sum**: We first calculate the sum of all elements in the array.\n2. **Track Frequencies**: Use an unordered map (`unordered_map<int, int> freq`) to count the occurrences of each element.\n3. **Iterate Through the Array**: For each element:\n   - Calculate the new sum by removing the current element.\n   - If this new sum is even, check if half of the new sum exists in the array.\n   - If it does, update the result with the largest valid outlier.\n4. **Final Check**: If no valid outlier is found, return `-1` as the answer.\n\n---\n\n### Complexity:\n\n- **Time complexity**:\n  - Building the frequency map (`unordered_map`) takes $$O(n)$$ time, where $$n$$ is the size of the array.\n  - Iterating through the array and checking conditions for each element also takes $$O(n)$$ time.\n  - The overall time complexity is $$O(n)$$.\n\n- **Space complexity**:\n  - The space complexity is $$O(n)$$ because we use an unordered map to store the frequency of each number in the array, which could store up to $$n$$ distinct numbers.\n\n---\n\n### Code:\n```cpp\nclass Solution {\npublic:\n    int getLargestOutlier(vector<int>& nums) {\n        int sum = 0;\n        unordered_map<int, int> freq;\n        \n        // Calculate the total sum and build the frequency map\n        for (int num : nums) {\n            sum += num;\n            freq[num]++;\n        }\n\n        int res = INT_MIN;  // Initialize result as the smallest possible integer\n\n        // Iterate over the array to check each number\n        for (int num : nums) {\n            int newSum = sum - num;  // New sum without the current element\n\n            // Check if the new sum is even\n            if (newSum % 2 == 0) {\n                int target = newSum / 2;  // Target value we need to check in the array\n\n                // If target exists and it\'s not the same number, or it\'s the same number but appears more than once\n                if ((target != num && freq.count(target)) ||\n                    (target == num && freq[num] > 1)) {\n                    res = max(res, num);  // Update the largest outlier found\n                }\n            }\n        }\n\n        return res == INT_MIN ? -1 : res;  // If no outlier is found, return -1\n    }\n};\n```\n\n---\n\n### Explanation:\n1. **Frequency Map**: We calculate the total sum of the array and simultaneously build a frequency map to keep track of how many times each number appears in the array.\n2. **Iterating Through Each Element**: For each element in the array:\n   - We compute the new sum after removing the current element.\n   - We then check if this new sum is even. If it is, we check if half of the new sum exists in the array (either different from the current element or multiple occurrences of the current element if it\'s the same).\n3. **Result Update**: If we find a valid outlier, we update the result with the largest such element.\n4. **Edge Case**: If no valid outlier is found, we return `-1`.\n\n---\n\nThis solution efficiently solves the problem by leveraging the frequency map for fast lookups and checking the outlier condition in linear time.
['C++']