Without Sorting O(n) in C++
IntuitionThe problem requires identifying an outlier in an array where:
n - 2 elements are special numbers.
One element is the sum of those special numbers.
The
# Intuition
The problem requires identifying an outlier in an array where:

- n - 2 elements are special numbers.
- One element is the sum of those special numbers.
- The remaining element is the outlier, which is not part of the sum.

To solve this:
1. Compute the total sum of the array.
2. Iterate through each number and check if removing it results in the remaining numbers forming a valid sum.
3. Find the largest valid outlier among the candidates.



# Complexity
- Time complexity:
    - O(N): First loop computes prefixSum and populates the unordered_set.
O(N): Second loop checks for valid outliers.
Overall: O(N) (since each lookup in unordered_set is O(1) on average).

- Space complexity:
    - O(N): We store all elements in unordered_set.

# Code
```cpp []
class Solution {
public:
    int getLargestOutlier(vector<int>& nums) {
        int size = nums.size();

        int prefixSum = 0;
        unordered_set<float> history;

        for (int i = 0; i < size; i++){
            prefixSum+=nums[i];
            history.insert(nums[i]);
        }
        int largestOutlier = INT_MIN;
        for (int i = 0; i < size; i++){
            if(history.find((prefixSum-nums[i])/2.0) != history.end() && (prefixSum-nums[i])/2.0 != nums[i] ){
                cout << prefixSum << nums[i] << endl ;
                largestOutlier = max(largestOutlier, nums[i]);
            }
        }
        
        if( largestOutlier == INT_MIN){
            for (int i = 0; i < size; i++){
                if(history.find((prefixSum-nums[i])/2.0) != history.end() ){
                    cout << prefixSum << nums[i] << endl ;
                    largestOutlier = max(largestOutlier, nums[i]);
                }
            }
        }
        return largestOutlier;
    }

};
```
['C++']