Easiest and Simplest Solution Ever in O(n)
Intuition\nThe problem revolves around identifying the largest outlier in the array. An outlier is defined as a number that is neither part of the n-2 special n
# Intuition\nThe problem revolves around identifying the largest outlier in the array. An outlier is defined as a number that is neither part of the `n-2` special numbers nor their sum. By using the total sum of the array, we can derive the sum of the `n-2` special numbers for each potential outlier and validate it.\n\n# Approach\n1. **Calculate Total Sum**:\n   Compute the sum of all numbers in the array. This helps derive the sum of the `n-2` special numbers for any given potential outlier.\n\n2. **Store Frequencies**:\n   Use an unordered map to store the frequency of each number for efficient lookups.\n\n3. **Iterate Through the Array**:\n   For each number in the array:\n   - Assume it is the outlier.\n   - Compute the sum of the `n-2` special numbers, x = (total_sum - num) / 2\n\n \n   - Ensure \\(x\\) is an integer and exists in the array.\n\n4. **Validate Candidates**:\n   Check that:\n   - The sum is divisible by 2.\n   - \\(x\\) exists in the frequency map.\n   - \\(x\\) and the candidate outlier are distinct or \\(x\\) occurs more than once.\n\n5. **Update Maximum Outlier**:\n   Track the largest valid outlier during the iteration.\n\n6. **Return Result**:\n   After iterating through all numbers, return the maximum outlier found.\n\n# Complexity\n- **Time Complexity**:  \n  - \\(O(n)\\) to calculate the total sum.  \n  - \\(O(n)\\) to populate the frequency map.  \n  - \\(O(n)\\) to validate each candidate.  \n  Overall: \\(O(n)\\).\n\n- **Space Complexity**:  \n  - \\(O(n)\\) for the frequency map.  \n  Overall: \\(O(n)\\).\n\n# Code\n```cpp\nclass Solution {\npublic:\n    int getLargestOutlier(vector<int>& nums) {\n        // Step 1: Calculate the total sum of all elements in the array\n        int total_sum = accumulate(nums.begin(), nums.end(), 0);\n\n        // Step 2: Store the frequencies of elements in a map\n        unordered_map<int, int> freq;\n        for (int num : nums) {\n            freq[num]++;\n        }\n\n        int max_outlier = INT_MIN; // Initialize the maximum outlier to the smallest possible value\n\n        // Step 3: Iterate through each number in the array\n        for (int num : nums) {\n            // Calculate the potential sum of the n-2 special numbers\n            int x = (total_sum - num) / 2;\n\n            // Check if (total_sum - num) is divisible by 2 and x exists in the array\n            if ((total_sum - num) % 2 == 0 && freq[x] > 0) {\n                // Handle the case where x and num are the same and x appears only once\n                if (x == num && freq[x] <= 1) continue;\n\n                // Update the maximum outlier if the current num is larger\n                max_outlier = max(max_outlier, num);\n            }\n        }\n\n        return max_outlier; // Return the largest valid outlier\n    }\n};\n
['C++']